Slowed gait in patients with Parkinson’s disease (PD) can be improved when patients synchronize footsteps to isochronous metronome cues, but limited retention of such improvements suggest that permanent cueing regimes are needed for long-term improvements. If so, music might make permanent cueing regimes more pleasant, improving adherence; however, music cueing requires patients to synchronize movements to the “beat,” which might be difficult for patients with PD who tend to show weak beat perception. One solution may be to use high-groove music, which has high beat salience that may facilitate synchronization, and affective properties, which may improve motivation to move. As a first step to understanding how beat perception affects gait in complex neurological disorders, we examined how beat perception ability affected gait in neurotypical adults. Synchronization performance and gait parameters were assessed as healthy young adults with strong or weak beat perception synchronized to low-groove music, high-groove music, and metronome cues. High-groove music was predicted to elicit better synchronization than low-groove music, due to its higher beat salience. Two musical tempi, or rates, were used: (1) preferred tempo: beat rate matched to preferred step rate and (2) faster tempo: beat rate adjusted to 22.5% faster than preferred step rate. For both strong and weak beat-perceivers, synchronization performance was best with metronome cues, followed by high-groove music, and worst with low-groove music. In addition, high-groove music elicited longer and faster steps than low-groove music, both at preferred tempo and at faster tempo. Low-groove music was particularly detrimental to gait in weak beat-perceivers, who showed slower and shorter steps compared to uncued walking. The findings show that individual differences in beat perception affect gait when synchronizing footsteps to music, and have implications for using music in gait rehabilitation.