Domestication - the artificial selection of wild species to obtain variants with traits of human interest - was integral to the rise of complex societies. The oversupply of food was probably associated with the formalization of food preservation strategies through microbial fermentation. While considerable literature exists on the antiquity of fermented food, only few eukaryotic microbes have been studied so far for signs of domestication, less is known for bacteria. Here, we tested if cheese starter cultures harbour typical hallmarks of domestication by characterising over 100 community samples and over 100 individual strains isolated from historical and modern traditional Swiss cheese starter cultures. We find that cheese starter cultures have low genetic diversity both at the species and strain-level and maintained stable phenotypic traits. Molecular clock dating further suggests that the evolutionary origin of the bacteria approximately coincided with the first archaeological records of cheese making. Finally, we find evidence for ongoing genome decay and pseudogenization via transposon insertion related to a reduction of their niche breadth. Future work documenting the prevalence of these hallmarks across diverse fermented food systems and geographic regions will be key to unveiling the joint history of humanity with fermented food microbes.