Purpose: The aims of this study were to: (1) determine the relationships between maximum oxygen uptake (V˙ O2max) and walking economy during non-graded and graded walking among overweight women and (2) examine potential differences in V˙ O2max and walking economy before and after weight loss. Methods: One-hundred and twenty-four premenopausal women with a body mass index (BMI) between 27 and 30 kg/m2 were randomly assigned to one of three groups: (a) diet only; (b) diet and aerobic exercise training; and (c) diet and resistance exercise training. All were furnished with standard, very-low calorie diet to reduce BMI to < 25 kg/m2. V˙ O2max was measured using a modified-Bruce protocol while walking economy (1-net V˙ O2) was obtained during fixed-speed (4.8 k·h−1), steady-state treadmill walking at 0% grade and 2.5% grade. Assessments were conducted before and after achieving target BMI. Results: Prior to weight loss, V˙ O2max was inversely related (P < 0.05) with non-graded and graded walking economy (r = − 0.28 to − 0.35). Similar results were also observed following weight loss (r = − 0.22 to − 0.28). Additionally, we also detected a significant inverse relationship (P < 0.05) between the changes (∆, after weight loss) in ∆V˙ O2max, adjusted for fat-free mass, with non-graded and graded ∆walking economy (r = − 0.37 to − 0.41). Conclusions: Our results demonstrate V˙ O2max and walking economy are inversely related (cross-sectional) before and after weight loss. Importantly though, ∆V˙ O2max and ∆walking economy were also found to be inversely related, suggesting a strong synchrony between maximal aerobic capacity and metabolic cost of exercise.