Lifestyle interventions with weight loss can improve insulin sensitivity in type 2 diabetes (T2D), but mechanisms are unclear. We explored circulating and skeletal muscle metabolite signatures of altered peripheral (pIS) and hepatic insulin sensitivity (hIS) in overweight and obese T2D individuals that were randomly assigned a 12-week Paleolithic-type diet with (diet-ex, n = 13) or without (diet, n = 13) supervised exercise. Baseline and post-intervention measures included: mass spectrometry-based metabolomics and lipidomics of skeletal muscle and plasma; pIS and hIS; ectopic lipid deposits in the liver and skeletal muscle; and skeletal muscle fat oxidation rate. Both groups lowered BMI and total % fat mass and increased their pIS. Only the diet-group improved hIS and reduced ectopic lipids in the liver and muscle. The combined improvement in pIS and hIS in the diet-group were associated with decreases in muscle and circulating branched-chain amino acid (BCAA) metabolites, specifically valine. Improved pIS with diet-ex was instead linked to increased diacylglycerol (34:2) and triacylglycerol (56:0) and decreased phosphatidylcholine (34:3) in muscle coupled with improved muscle fat oxidation rate. This suggests a tissue crosstalk involving BCAA-metabolites after diet intervention with improved pIS and hIS, reflecting reduced lipid influx. Increased skeletal muscle lipid utilization with exercise may prevent specific lipid accumulation at sites that perturb insulin signaling.