Endosymbiosis is a widespread phenomenon in the microbial world and can be based on diverse interactions between endosymbiont and host cell. The vast majority of the known endosymbiotic interactions involve bacteria that have invaded eukaryotic host cells. However, methanogenic archaea have been found to thrive in anaerobic, hydrogenosome-containing protists and it was suggested that this symbiosis is based on the transfer of hydrogen. Here, we used culture-independent genomics approaches to sequence the genomes of two distantly related methanogenic endosymbionts that have been acquired in two independent events by closely related anaerobic ciliate hosts Nyctotherus ovalis and Metopus contortus, respectively. The sequences obtained were then validated as originating from the ciliate endosymbionts by in situ probing experiments. Comparative analyses of these genomes and their closest free-living counterparts reveal that the genomes of both endosymbionts are in an early stage of adaptation towards endosymbiosis as evidenced by the large number of genes undergoing pseudogenization. For instance, the observed loss of genes involved in amino acid biosynthesis in both endosymbiont genomes indicates that the endosymbionts rely on their hosts for obtaining several essential nutrients. Furthermore, the endosymbionts appear to have gained significant amounts of genes of potentially secreted proteins, providing targets for future studies aiming to elucidate possible mechanisms underpinning host-interactions. Altogether, our results provide the first genomic insights into prokaryotic endosymbioses from the archaeal domain of life.