The invasive eucalyptus tortoise beetle, Paropsis charybdis, defoliates plantations of Eucalyptus nitens in New Zealand. Recent efforts to identify host specific biological control agents (parasitoids) from Tasmania, Australia, have focused on the larval parasitoid wasp, Eadya paropsidis (Braconidae), first described in 1978. In Tasmania, Eadya has been reared from Paropsisterna agricola (genus abbreviated Pst.), a smaller paropsine that feeds as a larva on juvenile rather than adult foliage of Eucalyptus nitens. To determine which of the many paropsine beetle hosts native to Tasmania are utilized by E. paropsidis, and to rule out the presence of cryptic species, a molecular phylogenetic approach was combined with host data from rearing experiments from multiple locations across six years. Sampling included 188 wasps and 94 beetles for molecular data alone. Two mitochondrial genes (COI and Cytb) and one nuclear gene (28S) were analyzed to assess the species limits in the parasitoid wasps. The mitochondrial genes were congruent in delimiting four separate phylogenetic species, all supported by morphological examinations of Eadya specimens collected throughout Tasmania. Eadya paropsidis was true to the type description, and was almost exclusively associated with P. tasmanica. A new cryptic species similar to E. paropsidis, Eadya sp. 3, was readily reared from Pst. agricola and P. charybdis from all sites and all years. Eadya sp. 3 represents the best candidate for biological control of P. charybdis and was determined as the species undergoing host range testing in New Zealand for its potential as a biological control agent. Another new species, Eadya sp. 1, was morphologically distinctive and attacked multiple hosts. The most common host was Pst. variicollis, but was also reared from Pst. nobilitata and Pst. selmani. Eadya sp. 1 may have potential for control against Pst. variicollis, a new incursion in New Zealand, and possibly Pst. selmani in Ireland. Our molecular data suggests that Pst. variicollis is in need of taxonomic revision and the geographic source of the beetle in New Zealand may not be Tasmania. Eadya sp. 2 was rarely collected and attacked P. aegrota elliotti and P. charybdis. Most species of Eadya present in Tasmania are not host specific to one beetle species alone, but demonstrate some host plasticity across the genera Paropsisterna and Paropsis. This study is an excellent example of collaborative phylogenetic and biological control research prior to the release of prospective biological control agents, and has important implications for the Eucalyptus industry worldwide.