The experiment reported in this research paper aimed to evaluate the effects of high-starch or starch and oil-supplemented diets on rumen and faecal bacteria, and explore links between the structure of bacterial communities and milk fatty acid (FA) profiles. We used four Holstein dairy cows in a 4 × 4 Latin square design. Cows were fed a diet rich in cereals (high-starch diet with 23% starch content on dry matter (DM) basis), a diet supplemented with saturated FA from Ca salts of palm oil + 18% DM starch, a diet with high content of monounsaturated FA (from extruded rapeseeds) + 18% DM starch or a diet rich in polyunsaturated FA (from extruded sunflower seeds) + 17% DM starch. At the end of each experimental period, cows were sampled for rumen and faecal contents, which were used for DNA extraction and amplicon sequencing. Partial least squares (PLS) regression analysis highlighted diet-related changes in both rumen and faecal bacterial structures. Sparse PLS discriminant analysis was further employed to identify biologically relevant operational taxonomical units (OTUs) driving these differences. Our results show that Butyrivibrio discriminated the high-starch diet and linked positively with higher concentrations of milk odd- and branched-chain FA. YS2-related OTUs were key taxa distinguishing diets supplemented with Ca salts of palm oil or sunflower seeds and correlated positively with linoleic acid in milk. Similarly, diets modulated faecal bacterial composition. However, correlations between changes in faecal and rumen bacteria were poor. With this work, we demonstrated that high-starch or lipid-supplemented diets affect rumen and faecal bacterial community structure, and these changes could have a knock-on effect on milk FA profiles.