Abstract Background Akkermansia muciniphila is a member of the human gut microbiota where it resides in the mucus layer and uses mucin as the sole carbon, nitrogen and energy source. A. muciniphila is the only representative of the Verrucomicrobia phylum in the human gut. However, A. muciniphila 16S rRNA gene sequences have also been found in the intestines of many vertebrates. Results We detected A. muciniphila-like bacteria in the intestines of animals belonging to 15 out of 16 mammalian orders. In addition, other species belonging to the Verrucomicrobia phylum were detected in fecal samples. We isolated 10 new A. muciniphila strains from the feces of chimpanzee, siamang, mouse, pig, reindeer, horse and elephant. The physiology and genome of these strains were highly similar in comparison to the type strain A. muciniphila Muc^T. Overall, the genomes of the new strains showed high average nucleotide identity (93.9 to 99.7%). In these genomes, we detected considerable conservation of at least 75 of the 78 mucin degradation genes that were previously detected in the genome of the type strain Muc^T. Conclusions The low genomic divergence observed in the new strains may indicate that A. muciniphila favors mucosal colonization independent of the differences in hosts. In addition, the conserved mucus degradation capability points towards a similar beneficial role of the new strains in regulating host metabolic health.