Fig-pollinating wasps have provided model systems for developing and testing theories of the evolution of mutualism, sex allocation, and precision of adaptation. With few exceptions, previous studies have assumed one species of pollinator wasp per host fig species. Here we report genetic data demonstrating the coexistence of previously undetected cryptic fig wasp species in at least half of the host fig species surveyed. The substantial mitochondrial sequence differences (4.2-6.1%) imply old divergences ( approximately 1.5-5.1 million years ago) among these species. Furthermore, some cryptic species pairs seem to be sister taxa, whereas others clearly are not, indicating both long-term coexistence on shared hosts and the colonization of novel fig species. These findings undermine the prevalent notion of strict one-to-one specificity between cospeciating figs and their pollinators, thereby challenging existing theory concerning the evolution and stability of mutualisms. Moreover, the incorporation of the genetic information significantly improves the fit of the observed sex ratios to predictions of local mate-competition theory, further strengthening support for sex allocation theory and the precision of adaptation.