Non-alcoholic fatty liver disease (NAFLD) is the most common liver disease, and its prevalence worldwide is increasing. Several studies support the pathophysiological role of the gut–liver axis, where specific signal pathways are finely tuned by intestinal microbiota both in the onset and progression of NAFLD. In the present study, we investigate the impact of different lifestyle interventions on the gut microbiota composition in 109 NAFLD patients randomly allocated to six lifestyle intervention groups: Low Glycemic Index Mediterranean Diet (LGIMD), aerobic activity program (ATFIS_1), combined activity program (ATFIS_2), LGIMD plus ATFIS_1 or ATFIS2 and Control Diet based on CREA-AN (INRAN). The relative abundances of microbial taxa at all taxonomic levels were explored in all the intervention groups and used to cluster samples based on a statistical approach, relying both on the discriminant analysis of principal components (DAPCs) and on a linear regression model. Our analyses reveal important differences when physical activity and the Mediterranean diet are merged as treatment and allow us to identify the most statistically significant taxa linked with liver protection. These findings agree with the decreased ‘controlled attenuation parameter’ (CAP) detected in the LGIMD-ATFIS_1 group, measured using FibroScan®. In conclusion, our study demonstrates the synergistic effect of lifestyle interventions (diet and/or physical activity programs) on the gut microbiota composition in NAFLD patients.