A comprehensive view of our evolutionary history cannot ignore the ancestral features of our gut microbiota. To provide some glimpse into the past, we searched for human gut microbiome components in ancient DNA from 14 archeological sediments spanning four stratigraphic units of El Salt Middle Paleolithic site (Spain), including layers of unit X, which has yielded well-preserved Neanderthal occupation deposits dating around 50 kya. According to our findings, bacterial genera belonging to families known to be part of the modern human gut microbiome are abundantly represented only across unit X samples, showing that well-known beneficial gut commensals, such as Blautia, Dorea, Roseburia, Ruminococcus, Faecalibacterium and Bifidobacterium already populated the intestinal microbiome of Homo since as far back as the last common ancestor between humans and Neanderthals.