The enemy release hypothesis posits that the initial success of invasive species depends on the scarcity and poor adaptation of native natural enemies such as predators and parasitoids. As for parasitoids, invading hosts are first attacked at low rates by a species-poor complex of mainly generalist species. Over the years, however, parasitoid richness may increase either because the invading host continuously encounters new parasitoid species during its spread (geographic spread-hypothesis) or because local parasitoids need different periods of time to adapt to the novel host (adjustment-hypothesis). Both scenarios should result in a continuous increase of parasitoid richness over time. In this study, we reconstructed the development of the hymenopteran parasitoid complex of the invasive leafminer Cameraria ohridella (Lepidoptera, Gracillariidae). Our results show that the overall parasitism rate increases as a function of host residence time as well as geographic and climatic factors, altogether reflecting the historic spread of C. ohridella. The same variables also explain the individual parasitism rates of several species in the parasitoid complex, but fail to explain the abundance of others. Evidence supporting the “geographic spread-hypothesis” was found in the parasitism pattern of Cirrospilus talitzkii (Hymenoptera, Eulophidae), while that of Pediobius saulius, another eulophid, indicated an increase of parasitism rates by behavioral, phenological or biological adjustments. Compared to fully integrated host-parasitoid associations, however, parasitism rates of C. ohridella are still very low. In addition, the parasitoid complex lacks specialists, provided that the species determined are valid and not complexes of cryptic (and presumably more specialized) species. Probably, the adjustment of specialist parasitoids requires more than a few decades, particularly to invaders which establish in ecological niches free of native hosts, thus eliminating any possibility of recruitment of pre-adapted parasitoids.