Background: Non-Alcoholic Fatty Liver Disease (NAFLD) is one the most prevalent causes of chronic liver disease worldwide. In the absence of an approved drug treatment, lifestyle modification is the first intervention strategy. This study aimed to estimate the main effect of two different physical activity (PA) programs, and a Low-Glycemic-Index Mediterranean Diet (LGIMD), or their combined effect on liver fibrosis parameters in subjects with NAFLD. Methods: Subjects with moderate or severe NAFLD grade of severity (n = 144) were randomly assigned to six intervention arms for three months: LGIMD, PA programs, and their combination. Data were collected at baseline, 45 days, and 90 days. Transient elastography was performed to assess the outcome. Results: at 90 days, a statistically significant reduction in kPa was found among subjects following LGMID (−2.85, 95% CI −5.24, −0.45) and those following an LGIMD plus PA1 (−2.37, 95% CI −4.39, −0.35) and LGIMD plus Pa2 (−2.21, 95% CI −4.10, −0.32). The contrast between time 2 and time 1 of the LGIMD plus PA2 treatment showed a statistically significant increase, and vice versa: the contrast between time 3 and time 2 of the same treatment showed a statistically significant reduction. The PA1 and PA2 arms also showed reduced kPa, although the results did not reach statistical significance. Conclusions: The intervention arms, LGIMD, LGIMD+PA1, and LGIMD+PA2, reduced the fibrosis score.