The endosymbiotic bacterium Wolbachia enhances its spread via vertical transmission by generating reproductive effects in its hosts, most notably cytoplasmic incompatibility (CI). Additionally, frequent interspecific horizontal transfer is evident from a lack of phylogenetic congruence between Wolbachia and its hosts. The mechanisms of this lateral transfer are largely unclear. To identify potential pathways of Wolbachia movements, we performed multilocus sequence typing of Wolbachia strains from bees (Anthophila). Using a host phylogeny and ecological data, we tested various models of horizontal endosymbiont transmission. In general, Wolbachia strains seem to be randomly distributed among bee hosts. Kleptoparasite-host associations among bees as well as other ecological links could not be supported as sole basis for the spread of Wolbachia. However, cophylogenetic analyses and divergence time estimations suggest that Wolbachia may persist within a host lineage over considerable timescales and that strictly vertical transmission and subsequent random loss of infections across lineages may have had a greater impact on Wolbachia strain distribution than previously estimated. Although general conclusions about Wolbachia movements among arthropod hosts cannot be made, we present a framework by which precise assumptions about shared evolutionary histories of Wolbachia and a host taxon can be modelled and tested.