The γ-proteobacterium Arsenophonus and its close relatives (Arsenophonus and like organisms, ALOs) are emerging as a novel clade of endosymbionts, which are exceptionally widespread in insects. The biology of ALOs is, however, in most cases entirely unknown, and it is unclear how these endosymbionts spread across insect populations. Here, we investigate this aspect through the examination of the presence, the diversity and the evolutionary history of ALOs in 25 related species of blood-feeding flies: tsetse flies (Glossinidae), louse flies (Hippoboscidae) and bat flies (Nycteribiidae and Streblidae). While these endosymbionts were not found in tsetse flies, we identify louse flies and bat flies as harbouring the highest diversity of ALO strains reported to date, including a novel ALO clade, as well as Arsenophonus and the recently described Candidatus Aschnera chinzeii clade. We further show that the origin of ALO endosymbiosies extends deep into the evolutionary past of louse flies and bat flies, and that it likely played a major role in the ecological specialization of their hosts. The evolutionary history of ALOs is notably complex and was shaped by both vertical transmission and horizontal transfers with frequent host turnover and apparent symbiont replacement in host lineages. In particular, ALOs have evolved repeatedly and independently close relationships with diverse groups of louse flies and bat flies, as well as phylogenetically more distant insect families, suggesting that ALO endosymbioses are exceptionally dynamic systems.