Background: Stroke-induced immunosuppression (SII) represents a negative rehabilitative prognostic factor associated with poor motor performance at discharge from a neurorehabilitation unit (NRB). This study aims to evaluate the association between SII and gait impairment at NRB admission. Methods: Forty-six stroke patients (65.4 ± 15.8 years, 28 males) and 42 healthy subjects (HS), matched for age, sex, and gait speed, underwent gait analysis using an inertial measurement unit at the lumbar level. Stroke patients were divided into two groups: (i) the SII group was defined using a neutrophil-to-lymphocyte ratio ≥ 5, and (ii) the immunocompetent (IC) group. Harmonic ratio (HR) and short-term largest Lyapunov’s exponent (sLLE) were calculated as measures of gait symmetry and stability, respectively. Results: Out of 46 patients, 14 (30.4%) had SII. HR was higher in HS when compared to SII and IC groups (p p p ≤ 0.01 for all comparisons). sLLE in the medio-lateral plane was higher in SII when compared to IC subjects (p = 0.04). Conclusions: SII individuals are characterized by a pronounced asymmetric gait and a more impaired dynamic gait stability. Our findings underline the importance of devising tailored rehabilitation programs in patients with SII. Further studies are needed to assess the long-term outcomes and the role of other clinical features on gait pattern.