For centuries humans have been fascinated by the natural beauty of horses in motion and their different gaits. Gait classification (GC) is commonly performed through visual assessment and reliable, automated methods for real-time objective GC in horses are warranted. In this study, we used a full body network of wireless, high sampling-rate sensors combined with machine learning to fully automatically classify gait. Using data from 120 horses of four different domestic breeds, equipped with seven motion sensors, we included 7576 strides from eight different gaits. GC was trained using several machine-learning approaches, both from feature-extracted data and from raw sensor data. Our best GC model achieved 97% accuracy. Our technique facilitated accurate, GC that enables in-depth biomechanical studies and allows for highly accurate phenotyping of gait for genetic research and breeding. Our approach lends itself for potential use in other quadrupedal species without the need for developing gait/animal specific algorithms.