Introduction: The physical health of students is an indispensable part of the education system. Objectives: The existing methods for evaluating physical fitness and health lack sufficient analysis of test data. Methods: Therefore, the study proposed an improved student physical health evaluation algorithm using K-means and decision tree algorithms. The initial cluster center of K-means was determined using cuckoo optimization, and the median distance of data points was used instead of the mean. The minimum Gini coefficient was used as the optimal binary value for the decision tree algorithm. Results: Experiments showed that the root mean square error of each item in the improved K-means algorithm was on average 0.056 lower than that of the fuzzy C-means algorithm. The recall rate and F1 value were on average 0.084 and 0.093 higher, respectively. The accuracy of clustering analysis was 3.3% and 5.1% higher than that of the FC-MC algorithm and SC algorithm, respectively. The decision tree algorithm approached convergence after 200 iterations, with the maximum values being 1.4%, 6.3%, and 13.5% higher than other algorithms. In the randomly selected class, the contribution of male students’ sitting forward bending, long-distance running, and pull-up projects to the total score was relatively low and need to be prioritized for improvement. Conclusion: From this, the proposed physical health evaluation method can effectively minimize the impact of extreme value data on the calculation outcomes, raise the accuracy of clustering analysis and evaluation, and accurately determine the overall and individual physical weakness items of the class.