Physical deconditioning after stroke may induce post-stroke fatigue. However, research on this association is limited. Our primary objective was to investigate the associations of post-stroke fatigue severity with oxygen uptake ([Formula: see text]O2) at peak exercise and the time constant of [Formula: see text]O2 kinetics (τ[Formula: see text]O2) at exercise onset. The secondary objective was to examine the associations between fatigue and cardiorespiratory variables potentially affecting [Formula: see text]O2 during exercise. Twenty-three inpatients from a subacute rehabilitation ward were enrolled in this study. The median (interquartile range) Fatigue Severity Scale (FSS) score, as a measure of fatigue, was 32 (range 27-42) points. The FSS score was not associated with [Formula: see text]O2 at peak exercise during a symptom-limited graded exercise test (rho = - 0.264; p = 0.224), whereas it was significantly associated with τ[Formula: see text]O2 during a submaximal constant-load exercise test (rho = 0.530; p = 0.009). A higher FSS score also significantly correlated with a longer time constant of cardiac output (CO) kinetics (rho = 0.476; p = 0.022). Our findings suggest that severe post-stroke fatigue is associated with delayed increases in [Formula: see text]O2 and CO at the onset of exercise. Our findings can contribute to the development of an appropriate rehabilitation programme for individuals with post-stroke fatigue.