The expressive features of music can influence the velocity of walking. So far, studies used instructed (and intended) synchronization. But is this velocity effect still present with non-instructed (spontaneous) synchronization? To figure that out, participants were instructed to walk in their own comfort tempo on an indoor track, first in silence and then with tempo-matched music. We compared velocities of silence and music conditions. The results show that some music has an activating influence, increasing velocity and motivation, while other music has a relaxing influence, decreasing velocity and motivation. The influence of musical expression on the velocity of self-paced walking can be predicted with a regression model using only three sonic features explaining 56% of the variance. Phase-coherence between footfall and beat did not contribute to the velocity effect, due to its implied fixed pacing. The findings suggest that the velocity effect depends on vigor entrainment that influences both stride length and pacing. Our findings are relevant for preventing injuries, for gait improvement in walking rehabilitation, and for improving performance in sports activities.