Abstract: Methanogenic endosymbionts are the only known intracellular archaeans and are especially common in anaerobic ciliated protists. Studies on the evolution of associations between anaerobic ciliates and their methanogenic endosymbionts offer an excellent opportunity to broaden our knowledge about symbiosis theory and adaptation of eukaryotes to anoxic environments. Here, the diversity of methanogenic endosymbionts was analyzed with the addition of nine anaerobic ciliate populations that were newly studied by various methods. Results showed that diverse anaerobic ciliates host methanogenic endosymbionts that are limited to a few genera in orders Methanomicrobiales, Methanobacteriales, and Methanosarcinales. For the first time, anaerobic ciliates of the classes Muranotrichea and Prostomatea were found to host methanogenic endosymbionts. Distinct origins of endosymbiosis were revealed for classes Armophorea and Plagiopylea. We posit that armophoreans and plagiopyleans might have harbored Methanoregula (order Methanomicrobiales) and Methanocorpusculum (order Methanomicrobiales), respectively, as methanogenic endosymbionts at the beginning of their evolution. Subsequently, independent endosymbiont replacement events occurred in methanogen-ciliate associations, probably due to ecological transitions, species radiation of ciliate hosts, and vertical transmission bottlenecks of endosymbionts. Our results shed light on the evolution of associations between anaerobic ciliates and methanogens, and identifies the necessary preconditions for illustrating mechanisms by which endosymbioses between these partners were established.