Entraining human gait with a periodic mechanical perturbation has been proposed as a potentially effective strategy for gait rehabilitation, but the related studies have mostly depended on the use of a fixed-speed treadmill (FST) due to various practical constraints. However, imposing a constant treadmill speed on participants becomes a critical problem because this speed constraint prohibits the participants from adjusting the gait speed, resulting in significant alterations in natural biomechanics as the entrainment alters the stride frequency. In this study, we hypothesized that the use of a variable-speed treadmill (VST), which enables the participants to continuously adjust their speed, can improve the success rate of gait entrainment and preserve natural gait biomechanics. To test this hypothesis, we recruited 15 young and healthy adults and let them walk on a conventional FST and a self-paced VST while wearing a soft robotic hip exosuit, which applied hip flexion perturbations at various frequencies, ranging from the preferred walking frequency to a 30% increased value. Kinematics and kinetics of the participants' walking under the two treadmill conditions were measured on two separate days. Experimental results demonstrated a higher success rate of entrainment during VST walking compared to FST walking, particularly at faster perturbation frequencies. Furthermore, walking on VST facilitated the maintenance of natural biomechanics, such as stride length and normalized propulsive impulse, better than walking on FST. The observed improvement, primarily attributed to allowing an increase in walking speed following the increase in the perturbation frequency, suggests that using a self-paced VST is a viable method for exploiting the potentially beneficial therapeutic effects of entrainment in gait rehabilitation.