Blood lactate accumulation is a crucial fatigue indicator during sports training. Previous studies have predicted cycling fatigue using surface-electromyography (sEMG) to non-invasively estimate lactate concentration in blood. This study used sEMG to predict muscle fatigue while running and proposes a novel method for the automatic classification of running fatigue based on sEMG. Data were acquired from 12 runners during an incremental treadmill running-test using sEMG sensors placed on the vastus-lateralis, vastus-medialis, biceps-femoris, semitendinosus, and gastrocnemius muscles of the right and left legs. Blood lactate samples of each runner were collected every two minutes during the test. A change-point segmentation algorithm labeled each sample with a class of fatigue level as (1) aerobic, (2) anaerobic, or (3) recovery. Three separate random forest models were trained to classify fatigue using 36 frequency, 51 time-domain, and 36 time-event sEMG features. The models were optimized using a forward sequential feature elimination algorithm. Results showed that the random forest trained using distributive power frequency of the sEMG signal of the vastus-lateralis muscle alone could classify fatigue with high accuracy. Importantly for this feature, group-mean ranks were significantly different (p < 0.01) between fatigue classes. Findings support using this model for monitoring fatigue levels during running. © 2019 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (http://creativecommons.org/licenses/by/4.0/).