The extent and speed of transient skeletal muscle deoxygenation during exercise onset in patients with chronic heart failure (CHF) are related to impairments of local O2 delivery and utilization. This study examined the physiological background of submaximal exercise performance in 19 moderately impaired patients with CHF (Weber class A, B, and C) compared with 19 matched healthy control (HC) subjects by measuring skeletal muscle oxygenation (SmO2) changes during cycling exercise. All subjects performed two subsequent moderate-intensity 6-min exercise tests (bouts 1 and 2) with measurements of pulmonary oxygen uptake kinetics and SmO2 using near-infrared spatially resolved spectroscopy at the vastus lateralis for determination of absolute oxygenation values, amplitudes, kinetics (mean response time for onset), and deoxygenation overshoot characteristics. In CHF, deoxygenation kinetics were slower compared with HC (21.3 ± 5.3 s vs. 16.7 ± 4.4 s, P < 0.05, respectively). After priming exercise (i.e., during bout 2), deoxygenation kinetics were accelerated in CHF to values no longer different from HC (16.9 ± 4.6 s vs. 15.4 ± 4.2 s, P = 0.35). However, priming did not speed deoxygenation kinetics in CHF subjects with a deoxygenation overshoot, whereas it did reduce the incidence of the overshoot in this specific group (P < 0.05). These results provide evidence for heterogeneity with respect to limitations of O2 delivery and utilization during moderate-intensity exercise in patients with CHF, with slowed deoxygenation kinetics indicating a predominant O2 utilization impairment and the presence of a deoxygenation overshoot, with a reduction after priming in a subgroup, indicating an initial O2 delivery to utilization mismatch.