The modern Paleolithic diet (MPD), featured by the consumption of vegetables, fruit, nuts, seeds, eggs, fish and lean meat, while excluding grains, dairy products, salt and refined sugar, has gained substantial public attention in recent years because of its potential multiple health benefits. However, to date little is known about the actual impact of this dietary pattern on the gut microbiome (GM) and its implications for human health. In the current scenario where Western diets, low in fiber while rich in industrialized and processed foods, are considered one of the leading causes of maladaptive GM changes along human evolution, likely contributing to the increasing incidence of chronic non-communicable diseases, we hypothesize that the MPD could modulate the Western GM towards a more "ancestral" configuration. In an attempt to shed light on this, here we profiled the GM structure of urban Italian subjects adhering to the MPD, and compared data with other urban Italians following a Mediterranean Diet (MD), as well as worldwide traditional hunter-gatherer populations from previous publications. Notwithstanding a strong geography effect on the GM structure, our results show an unexpectedly high degree of biodiversity in MPD subjects, which well approximates that of traditional populations. The GM of MPD individuals also shows some peculiarities, including a high relative abundance of bile-tolerant and fat-loving microorganisms. The consumption of plant-based foods-albeit with the exclusion of grains and pulses-along with the minimization of the intake of processed foods, both hallmarks of the MPD, could therefore contribute to partially rewild the GM but caution should be taken in adhering to this dietary pattern in the long term.