Energy expenditure (EE) during walking includes energy costs to move and support the body and for respiration and circulation. We measured EE during walking under three different oxygen concentrations. Eleven healthy, young, male lowlanders walked on a treadmill at seven gait speeds (0.67–1.83 m s−1) on a level gradient under normobaric normoxia (room air, 21% O2), moderate hypoxia (15% O2), and severe hypoxia (11% O2). By comparing the hypoxia-induced elevation in heart rate (HR [bpm]), ventilation (VE [L min−1]) with the change in energy expenditure (EE [W]) at each speed, we were able to determine circulatory and respiratory costs. In a multivariate model combining HR and VE, respiratory costs were 0.44 ± 0.15 W per each L min−1 increase in VE, and circulatory costs were 0.24 ± 0.05 W per each bpm increase in HR (model adjusted r2 = 0.97, p < 0.001). These VE costs were substantially lower than previous studies that ignored the contribution of HR to cardiopulmonary work. Estimated HR costs were consistent with, although somewhat higher than, measures derived from catheterization studies. Cardiopulmonary costs accounted for 23% of resting EE, but less than 5% of net walking costs (i.e., with resting EE subtracted).