Adenovirus (AdV) infections are one of the main causes of diarrhea in young children. Enteric AdVs probably disrupt gut microbial defences, which can result in diarrhea. To understand the role of the gut microbiome in AdV-induced pathologies, we investigated the gut microbiome of a naturally AdV-infected non-human primate species, the Malagasy mouse lemur (Microcebus griseorufus), which represents an important model in understanding the evolution of diseases. We observed that AdV infection is associated with disruption of the gut microbial community composition. In AdV+ lemurs, several commensal taxa essential for a healthy gut microbiome decreased, whereas genera containing potential pathogens, such as Neisseria, increased in abundance. Microbial co-occurrence networks revealed a loss of important microbial community interactions in AdV+ lemurs and an overrepresentation of Prevotellaceae. The observation of enteric virus-associated loss of commensal bacteria and associated shifts towards pathobionts may represent the missing link for a better understanding of AdV-induced effects in humans, and also for their potential as drivers of co-infections, an area of research that has been largely neglected so far.