Wolbachiaare very common, maternally transmitted endosymbionts of insects. They often spread by a mechanism termed cytoplasmic incompatibility (CI) that involves reduced egg hatch whenWolbachia-free ova are fertilized by sperm fromWolbachia-infected males. Because the progeny ofWolbachia-infected females generally do not suffer CI-induced mortality, infected females are often at a reproductive advantage in polymorphic populations. Deterministic models show thatWolbachiathat impose no costs on their hosts and have perfect maternal transmission will spread from arbitrarily low frequencies (though initially very slowly); otherwise, there will be a threshold frequency below whichWolbachiafrequencies decline to extinction and above which they increase to fixation or a high stable equilibrium. Stochastic theory was used to calculate the probability of fixation in populations of different size for arbitrary current frequencies ofWolbachia, with special attention paid to the case of spread after the arrival of a single infected female. Exact results are given based on a Moran process that assumes a specific demographic model, and approximate results are obtained using the more general Wright–Fisher theory. A new analytical approximation for the probability of fixation is derived, which performs well for small population sizes. The significance of stochastic effects in the natural spread ofWolbachiaand their relevance to the use ofWolbachiaas a drive mechanism in vector and pest management are discussed.