Purpose: The present study aims to analyze the relationship between cardiac autonomic control at rest—i.e., baseline Heart Rate Variability (HRV)—and metabolic flexibility assessed by means of the FATox and CHOox oxidation rates at the intensities of maximum fat and carbohydrate oxidation (MFO and MCO, respectively). Methods: Twenty-four active over-60 women (66.8 ± 4.4 years) had their HRV assessed with 10 min recordings under resting conditions, and this was analyzed with Kubios Scientific software. After this, an incremental submaximal cycling test, starting at 30 watts, with increments of 10 watts every 3 min 15 s was performed. FATox and CHOox were calculated in the last 60 s at each step, using Frayn’s equation. MFO and MCO were further obtained. Results: Nonlinear SampEn and 1-DFAα1 (Detrending Fluctuation Analysis score) at rest were both moderate and significantly (p < 0.05) related to FATox (r = 0.43, r = −0.40) and CHOox (r = −0.59, r = 0.41), as well as RER (r = −0.43, r = 0.43) at FATmax intensity. At the MCO intensity, no association was observed between HRV and oxidation rates. However, DFAα1 (r = −0.63, p < 0.05), the frequency ratio LF/HF (r = −0.63, p < 0.05), and the Poincaré ratio SD1/SD2 (r = 0.48, p < 0.05) were correlated with blood lactate concentration. Conclusion: These results support the autonomic resources hypothesis, suggesting that better autonomic function at rest is related to enhanced metabolic flexibility in postmenopausal women. They also underpin a comprehensive analysis of cardiovascular-autonomic health with aging. The results imply that non-linear DFAα1 and SampEn are appropriate to analyze this association in health of the aging cardiovascular-autonomic system. Graphical Abstract: (Figure presented.)