Several horse breeds have been specifically selected for the ability to exhibit alternative patterns of locomotion, or gaits. A premature stop codon in the gene DMRT3 is permissive for “gaitedness” across breeds. However, this mutation is nearly fixed in both American Standardbred trotters and pacers, which perform a diagonal and lateral gait, respectively, during harness racing. This suggests that modifying alleles must influence the preferred gait at racing speeds in these populations. A genome-wide association analysis for the ability to pace was performed in 542 Standardbred horses (n = 176 pacers, n = 366 trotters) with genotype data imputed to ~74,000 single nucleotide polymorphisms (SNPs). Nineteen SNPs on nine chromosomes (ECA1, 2, 6, 9, 17, 19, 23, 25, 31) reached genome-wide significance (p < 1.44 x 10−6). Variant discovery in regions of interest was carried out via whole-genome sequencing. A set of 303 variants from 22 chromosomes with putative modifying effects on gait was genotyped in 659 Standardbreds (n = 231 pacers, n = 428 trotters) using a high-throughput assay. Random forest classification analysis resulted in an out-of-box error rate of 0.61%. A conditional inference tree algorithm containing seven SNPs predicted status as a pacer or trotter with 99.1% accuracy and subsequently performed with 99.4% accuracy in an independently sampled population of 166 Standardbreds (n = 83 pacers, n = 83 trotters). This highly accurate algorithm could be used by owners/trainers to identify Standardbred horses with the potential to race as pacers or as trotters, according to the genotype identified, prior to initiating training and would enable fine-tuning of breeding programs with designed matings. Additional work is needed to determine both the algorithm’s utility in other gaited breeds and whether any of the predictive SNPs play a physiologically functional role in the tendency to pace or tag true functional alleles. Certain horse breeds have been developed over generations specifically for the ability to perform alternative patterns of movement, or gaits. Current understanding of the genetic basis for these gaits is limited to one known mutation apparently necessary, but not sufficient, for explaining variability in “gaitedness.” The Standardbred breed includes two distinct groups, trotters, which exhibit a two-beat gait in which the opposite forelimb and hind limb move together, and pacers, which exhibit an alternative two-beat gait where the legs on the same side of the body move together. Our long-term objective is to identify variants underlying the ability of certain Standardbreds to pace. In this study, we were able to identify several regions of the genome highly associated with pacing and, within these regions, a number of specific highly associated variants. Although the biological function of these variants has yet to be determined, we developed a model based on seven variants that was > 99% accurate in predicting whether an individual was a pacer or a trotter in two independent populations. This predictive model can be used by horse owners to make breeding and training decisions related to this economically important trait, and by scientists interested in understanding the biology of coordinated gait development.