Dietary restriction of the sulfur-containing amino acids methionine and cysteine (SAAR) improves body composition, enhances insulin sensitivity, and extends lifespan; benefits seen also with endurance exercise. Yet, the impact of SAAR on skeletal muscle remains largely unexplored. Here we demonstrate that one week of SAAR in sedentary, young, male mice increases endurance exercise capacity. Indirect calorimetry showed that SAAR increased lipid oxidation at rest and delayed the onset of carbohydrate utilization during exercise. Transcriptomic analysis revealed increased expression of genes involved in fatty acid catabolism especially in glycolytic muscle following SAAR. These findings were functionally supported by increased fatty acid circulatory turnover flux and muscle β-oxidation. Reducing lipid uptake from circulation through endothelial cell (EC)-specific CD36 deletion attenuated the running phenotype. Mechanistically, VEGF-signaling inhibition prevented exercise increases following SAAR, without affecting angiogenesis, implicating noncanonical VEGF signaling and EC CD36-dependent fatty acid transport in regulating exercise capacity by influencing muscle substrate availability.