Millions to billions of DNA sequences can now be generated from ancient skeletal remains thanks to the massive throughput of next-generation sequencing platforms. Except in cases of exceptional endogenous DNA preservation, most of the sequences isolated from fossil material do not originate from the specimen of interest, but instead reflect environmental organisms that colonized the specimen after death. Here, we characterize the microbial diversity recovered from seven ca. 200-13,000 year old horse bones collected from northern Siberia. We use a robust, taxonomy-based assignment approach to identify the microorganisms present in ancient DNA extracts and quantify their relative abundances. Our results suggest that molecular preservation niches exist within ancient samples that can potentially be used to characterize the environments from which the remains are recovered. In addition, microbial community profiling of the seven specimens revealed site-specific environmental signatures. These microbial communities appear to comprise mainly organisms that colonized the fossils recently. Our approach significantly extends the amount of useful data that can be recovered from ancient specimens using a shotgun sequencing approach. In future, it may be possible to correlate, for example, the accumulation of post-mortem DNA damage with the presence and/or abundance of particular microbes.