This paper presents methods for collecting and analyzing physiological and biomechanical data during recreational runs in order to classify an athletepsilas perceived fatigue state. Heart rate and its variability, running speed and stride frequency, GPS position and shoe heel compression were recorded continuously while runners moved freely outdoors. During their activity the sportsmen answered questions about their fatigue state in five-minute-intervals. Data from 84 one-hour-runs was collected for analysis. The data was analyzed using features computed for each step of the athlete to distinguish three levels of the runnerpsilas fatigue state with an accuracy of 75.3% across multiple study participants and 91.8% in the intraindividual case. The results show that for most participating runners, a heart rate variability periodogram feature and a step duration feature are best suited for classification of the perceived fatigue level. This information can be used to support sportsmen, for example by adapting their equipment to the specific needs of a fatigued athlete.