Fermented foods (FFs) are part of the cultural heritage of several populations, and their production dates back 8000 years. Over the last ~150 years, the microbial consortia of many of the most widespread FFs have been characterised, leading in some instances to the standardisation of their production. Nevertheless, limited knowledge exists about the microbial communities of local and traditional FFs and their possible effects on human health. Recent findings suggest they might be a valuable source of novel probiotic strains, enriched in nutrients and highly sustainable for the environment. Despite the increasing number of observational studies and randomised controlled trials, it still remains unclear whether and how regular FF consumption is linked with health outcomes and enrichment of the gut microbiome in health-associated species. This review aims to sum up the knowledge about traditional FFs and their associated microbiomes, outlining the role of fermentation with respect to boosting nutritional profiles and attempting to establish a link between FF consumption and health-beneficial outcomes.