Myotragus balearicus was a small-sized caprine that lived in the Balearic Islands (Western Mediterranean Sea), and that became extinct around 4000 years ago. We extracted DNA from a Holocene coprolite (fossilized feces) from M. balearicus, and prepared double-stranded (DSL) and single-stranded (SSL) DNA libraries. Then we performed shotgun sequencing on the two library types DSL and SSL. To minimise DNA contamination, experiments were conducted in a laboratory dedicated to ancient DNA research, and strict filtering of the metagenomic data was performed using extraction blank controls and environmental data (soil, freshwater and air). Results show that the gut microbiome of M. balearicus is dominated by Actinobacteria, Firmicutes and Proteobacteria. Typical gut dwellers of ruminants, including Ruminococcus, Runimiclostridium, and methanogenic archaea, are also found in the coprolite. Before filtering, a significant increase in salt-tolerant and environmental microbes is found in SSL data when compared to DSL. However, we do not observe any difference in diversity and abundance between DSL and SSL datasets after filtering and normalisation. Thus, SSL may not be an ideal approach for maximising the sequencing effort in paleo-metagenomic studies due to the potentially higher risk of capturing environmental DNA contaminants.