The mechanisms by which exercise benefits patients with non-alcoholic fatty liver disease (NAFLD), the most common liver disease worldwide, remain poorly understood. A non-targeted liquid chromatography-mass spectrometry (LC-MS)-based metabolomics analysis was used to identify metabolic changes associated with NAFLD in humans upon exercise intervention (without diet change) across four different sample types-adipose tissue (AT), plasma, urine, and stool. Altogether, 46 subjects with NAFLD participated in this randomized controlled intervention study. The intervention group (n = 21) performed high-intensity interval training (HIIT) for 12 weeks while the control group (n = 25) kept their sedentary lifestyle. The participants' clinical parameters and metabolic profiles were compared between baseline and endpoint. HIIT significantly decreased fasting plasma glucose concentration (p = 0.027) and waist circumference (p = 0.028); and increased maximum oxygen consumption rate and maximum achieved workload (p < 0.001). HIIT resulted in sample-type-specific metabolite changes, including accumulation of amino acids and their derivatives in AT and plasma, while decreasing in urine and stool. Moreover, many of the metabolite level changes especially in the AT were correlated with the clinical parameters monitored during the intervention. In addition, certain lipids increased in plasma and decreased in the stool. Glyco-conjugated bile acids decreased in AT and urine. The 12-week HIIT exercise intervention has beneficial ameliorating effects in NAFLD subjects on a whole-body level, even without dietary changes and weight loss. The metabolomics analysis applied to the four different sample matrices provided an overall view on several metabolic pathways that had tissue-type specific changes after HIIT intervention in subjects with NAFLD. The results highlight especially the role of AT in responding to the HIIT challenge, and suggest that altered amino acid metabolism in AT might play a critical role in e.g. improving fasting plasma glucose concentration.