Wolbachia is one of the most common symbionts of arthropods. Its establishment requires lateral transfer to and successful transmission within novel host species. However, Wolbachia performs poorly when introduced into new host species, and models predict that Wolbachia should seldom be able to establish from low initial frequencies. Recently, various symbionts, including Wolbachia, have been shown to protect their hosts from natural enemies. Hence, Wolbachia invasion may be facilitated by the dynamic interaction between it, its host, and a natural enemy. We model such an interaction whereby Wolbachia induces either complete resistance, partial resistance, or tolerance to a host-specific pathogen and also induces the common manipulation phenotype of cytoplasmic incompatibility (CI). We show that the presence of the pathogen greatly facilitates Wolbachia invasion from rare and widens the parameter space in which “imperfect” Wolbachia strains can invade. Furthermore, positive frequency-dependent selection through CI can drive Wolbachia to very high frequencies, potentially excluding the pathogen. These results may explain a poorly understood aspect of Wolbachia biology: it is widespread, despite performing poorly after transfer to new host species. They also support the intriguing possibility that Wolbachia strains that encode both CI and natural-enemy resistance could potentially rid insects, including human disease vectors, of important pathogens.