Shoveling activity is a risky activity among the main transportation maintenance tasks, causing common physical injuries and fatigue. While subjective measures such as Borg’s Rating of Perceived Exertion (RPE) and physiological measures such as heart rate (HR) have been used to detect physical fatigue, previous studies have not classified the physical fatigue in shoveling asphalt. To address the gap, this study aims to classify physical fatigue using machine learning-based methods, among transportation maintenance workers during shoveling asphalt. Two types of data sources were collected, including subjective response (Borg RPE) and physiological responses (heart rate, electrodermal activity, and skin temperature). Six machine learning models were applied to classify physical fatigue, and the 10-fold cross validation was used to validate the models. Main research findings are: (1) most workers viewed shoveling asphalt as a light task; (2) the Random Forest and Decision Tree algorithms had the highest accuracy above 99% in fatigue classification. This research contributes to the potential of applying these methods to advance fatigue monitoring in the workplace, thus enhancing occupational safety.