Paleofeces are an important source of information to study the evolution of dietary habits and human health. The UNESCO World Heritage region of Hallstatt-Dachstein/Salzkammergut is one of Europe’s oldest cultural and industrial landscapes; its underground salt mines dating back at least to the 14th century BC are one of the few archaeological sites where paleofeces are well preserved. The high salt concentrations and the constant annual temperature at around 8°C inside the isolated Hallstatt mines have perfectly preserved organic archaeological artefacts (e.g. paleofeces, clothing, mining tools) that provide unique insights into the daily life of a progressive community in Hallstatt. Here we subjected human paleofeces dated from the Bronze Age to early Modern Times to an in-depth microscopic, metagenomic and proteomic analysis. This allowed us to reconstruct the diet of the former population and gain insights into their ancient gut microbiome composition. Our dietary survey identified bran and glumes of different cereals as one of the most prevalent plant fragments. This highly fibrous, carbohydrate-rich diet was supplemented with proteins from broad beans and occasionally with fruits, nuts, or animal food. Linked to these traditional dietary habits all ancient miners up to the early Modern times have gut microbiome structures akin to modern non-Westernized individuals which may indicate a shift in the gut community composition of modern Westernized populations due to quite recent dietary and lifestyle changes. When we extended our microbial survey to fungi present in the paleofeces, we observed in one of the Iron Age samples a high abundance of Penicillium roqueforti and Saccharomyces cerevisiae DNA. Genome-wide analysis indicates that both fungi were involved in food fermentation and provide the first molecular evidence for blue cheese and beer consumption during Iron Age Europe.