Construction is known for being a labor-intensive and risky industry. Within various occupational settings such as construction, physical fatigue is an underlying health condition that may lead to musculoskeletal disorders and fall-related injuries. Identifying a worker’s physical fatigue could enable safety managers to mitigate fatigue-related injuries and improve workplace operations. However, current physical fatigue assessment and identification methods include subjective, physiological, biomechanical, and computer vision approaches, which may be unreliable, intrusive, and require extensive post-processing, thus, rendering them impractical for continuous monitoring of workers’ movements and automated identification of physical fatigue. Given the above, this study aims to utilize a wearable insole device to identify and classify physical fatigue levels in construction workers. Ten asymptomatic subjects were recruited to perform a fatiguing manual rebar tying activity in a laboratory setting. Borg’s rating of perceived exertion (RPE) was applied as a subjective measure for collecting the levels of physical fatigue of each subject. Three sub-classification problems for identifying physical fatigue levels (i.e., PFL1, PFL2, and PFL3) were assessed. Numerous features were evaluated from the collected data samples after data segmentation. The classification performance of supervised machine learning algorithms was evaluated at a sliding window of 2.56 s. Our results from 10-fold cross-validation show an accuracy of 86% for the Random Forest (RF) algorithm, indicating the best performance among other algorithms. In addition, precision, recall, specificity, and F1-score metrics of the RF algorithm were between 52.63% to 82.62%, 52.63% to 84.32%, 89.60% to 92.33%, and 52.63% to 83.46%, respectively. These results indicate that data samples such as acceleration and plantar pressure acquired from a wearable insole device are reliable for identifying and classifying physical fatigue levels in construction workers. In summary, this study would contribute to providing a proactive physical fatigue assessment method and guidelines for early identification of physical fatigue in construction.