The aim of this study was to assess the ability of multiscale sample entropy (MSE), refined composite multiscale entropy (RCMSE), and complexity index (CI) to characterize gait complexity through trunk acceleration patterns in subjects with Parkinson’s disease (swPD) and healthy subjects, regardless of age or gait speed. The trunk acceleration patterns of 51 swPD and 50 healthy subjects (HS) were acquired using a lumbar-mounted magneto-inertial measurement unit during their walking. MSE, RCMSE, and CI were calculated on 2000 data points, using scale factors (τ) 1–6. Differences between swPD and HS were calculated at each τ, and the area under the receiver operating characteristics, optimal cutoff points, post-test probabilities, and diagnostic odds ratios were calculated. MSE, RCMSE, and CIs showed to differentiate swPD from HS. MSE in the anteroposterior direction at τ4 and τ5, and MSE in the ML direction at τ4 showed to characterize the gait disorders of swPD with the best trade-off between positive and negative posttest probabilities and correlated with the motor disability, pelvic kinematics, and stance phase. Using a time series of 2000 data points, a scale factor of 4 or 5 in the MSE procedure can yield the best trade-off in terms of post-test probabilities when compared to other scale factors for detecting gait variability and complexity in swPD.