Oxygen uptake efficiency slope (OUES) and excess post-exercise oxygen consumption (EPOC) are markers of physical fitness in the general population but have never been characterized in sickle cell anemia (SCA) where hematological and hemorheological properties are severely altered. Eight SCA patients and eleven healthy subjects (CONT) performed a submaximal incremental exercise conducted until the first ventilatory threshold (VT1). OUES was calculated from the data collected during the incremental period and EPOC parameters (amplitude [A] and time constant [τ]) were calculated from the data measured during exercise recovery. We found that OUES (p = 0.007) and A (p = 0.010) were lower, and τ (p = 0.035) was higher, in SCA patients compared to CONT subjects. OUES and τ were significantly correlated with hematocrit, red blood cell (RBC) deformability and RBC aggregates strength. Our findings suggest that both the abilities to use oxygen during exercise and to recover after a physical activity are impaired in SCA patients. This poor physical fitness seems to depend on the degree of anemia and RBC rheological alterations.