Wolbachia are cytoplasmically inherited bacteria that cause a number of reproductive alterations in insects, including cytoplasmic incompatibility, an incompatibility between sperm and egg that results in loss of sperm chromosomes following fertilization. Wolbachia are estimated to infect 15-20% of all insect species, and also are common in arachnids, isopods and nematodes. Therefore, Wolbachia-induced cytoplasmic incompatibility could be an important factor promoting rapid speciation in invertebrates, although this contention is controversial. Here we show that high levels of bidirectional cytoplasmic incompatibility between two closely related species of insects (the parasitic wasps Nasonia giraulti and Nasonia longicornis) preceded the evolution of other postmating reproductive barriers. The presence of Wolbachia severely reduces the frequency of hybrid offspring in interspecies crosses. However, antibiotic curing of the insects results in production of hybrids. Furthermore, F1 and F2 hybrids are completely viable and fertile, indicating the absence of F1 and F2 hybrid breakdown. Partial interspecific sexual isolation occurs, yet it is asymmetric and incomplete. Our results indicate that Wolbachia-induced reproductive isolation occurred in the early stages of speciation in this system, before the evolution of other postmating isolating mechanisms (for example, hybrid inviability and hybrid sterility).