It is unknown how plasma leptin affects fat oxidation depending on sex in young adults. Therefore, the present cross-sectional study aimed to examine the associations of plasma leptin with resting fat oxidation (RFO), maximal fat oxidation during exercise (MFO), and insulin sensitivity, considering the different responses in men and women, and the mediating role of fatness and cardiorespiratory fitness (CRF). Sixty-five young adults (22.5 ± 4.3 years; body mass index = 25.2 ± 4.7 kg·m−2, 23 females) participated in this study. Fasting plasma glucose, insulin, and leptin were analyzed. Variables related to insulin resistance (HOMA1-IR, HOMA2-IR), secretion (HOMA-%β), and sensitivity (HOMA-%S, QUICKI) were computed. RFO and MFO were determined through indirect calorimetry. A peak oxygen uptake (VO2peak) test was performed until exhaustion after the MFO test. The MFO was relativized to body mass (MFO-BM) and the legs’ lean mass divided by the height squared (MFO-LI). In men, leptin was negatively associated with MFO-BM and positively with HOMA-%β (p ≤ 0.02 in both). In women, leptin was positively associated with RFO and QUICKI, and negatively with MFO-BM (p p p > 0.05). Plasma leptin is associated with fat oxidation and insulin secretion/sensitivity, with different responses within each sex. The association between leptin and fat oxidation is mediated by cardiorespiratory fitness.