Fergusobia nematodes (Tylenchida: Fergusobiinae) and Fergusonina flies (Diptera: Fergusoninidae) are putative mutualists that develop together in galls formed in meristematic tissues of many species of the plant family Myrtaceae in Australasia. Fergusobia nematodes were sampled from a variety of myrtaceous hosts and gall types from Australia and one location in New Zealand between 1999 and 2006. Evolutionary relationships of these isolates were inferred from phylogenetic analyses of the DNA sequences of the nuclear ribosomal DNA near-full length small subunit (up to 1689bp for 21 isolates), partial large subunit D2/D3 domain (up to 889bp for 87 isolates), partial mitochondrial cytochrome oxidase subunit I (618 bp for 82 isolates), and combined D2/D3 and mtCOI (up to 1497bp for 66 isolates). The SSU data supported a monophyletic Fergusobia genus within a paraphyletic Howardula. A clade of Drosophila-associated Howardula, including Howardula aoronymphium, was the closest sequenced sister group. Phylogenetic analysis of sequences from D2/D3 and mtCOI, separately and combined, revealed many monophyletic clades within Fergusobia. The relationships inferred by D2/D3 and mtCOI were congruent with some exceptions. Well-supported clades were generally consistent with host plant species and gall type. However, phylogenetic analysis suggested host switching or putative hybridization events in many groups, except the lineage of shoot bud gallers on the broad-leaved Melaleuca species complex.