We surveyed the parasitoid complex associated with four non-pest tephritid flies in Hawaii, Procecidochares alani Steyskal (on the Island of Hawaii), and Eutreta xanthochaeta Aldrich, Phaeogramma lortnocoibon Asquith, and Trupanea dubautiae (Byran) (on the island of Kauai). The former two tephritids are deliberately-introduced biological control agents of weeds; and the latter two are endemic to the Hawaiian Islands. Ten species of hymenopterous parasitoids in six families were recovered from these four non-pest tephritids. Among these species of parasitoids, six were inadvertently introduced to Hawaii, including Eurytoma tephritidis Fullaway (Eurytomidae), Bracon terryi (Bridwell) (Braconidae), Habrocytus elevatus (Walker) (Pteromalidae), Euderus metallicus (Ashmead) (Eulophidae), Torymus advenus (Osten Sacken) (Torymidae), and Eupelmus allynii (French) (Eupelmidae); and three were purposely introduced to Hawaii for classical biological control of economically important pests, including Eupelmus cushmani (Crawford), Diachasmimorpha tryoni (Cameron), (Braconidae), and Diachasmimorpha longicaudata (Ashmead). The relative abundance of parasitoid species and percent parasitism varied with the tephritid hosts. Our findings indicate that future development and implementation of biological control programs against frugivorous tephritids or other pests should consider the potential impact of some of the parasitoids on deliberately-introduced weed control agents. Before we can fully assess the potential impacts of some of the purposely-introduced parasitoids on non-target tephritids, however, effects of the many vagrant parasitoids associated with the non-targets should be thoroughly investigated.