Ancient genomic studies have extensively explored human-microbial interactions, yet research on non-human animals remains limited. In this study, we analyzed ancient microbial DNA from 483 mammoth remains spanning over 1 million years, including 440 newly sequenced and unpublished samples from a 1.1-million-year-old steppe mammoth. Using metagenomic screening, contaminant filtering, damage pattern analysis, and phylogenetic inference, we identified 310 microbes associated with different mammoth tissues. While most microbes were environmental or post-mortem colonizers, we recovered genomic evidence of six host-associated microbial clades spanning Actinobacillus, Pasteurella, Streptococcus, and Erysipelothrix. Some of these clades contained putative virulence factors, including a Pasteurella-related bacterium that had previously been linked to the deaths of African elephants. Notably, we reconstructed partial genomes of Erysipelothrix from the oldest mammoth sample, representing the oldest authenticated host-associated microbial DNA to date. This work demonstrates the potential of obtaining ancient animal microbiomes, which can inform further paleoecological and evolutionary research.