The assessment findings are given too much weight in the current system of evaluation for physical education instruction at higher education institutions. In contrast, the method of teaching and students’ basic health literacy are given insufficient weight. To address this phenomenon, this paper utilizes educational evaluation theory, fuzzy comprehensive evaluation theory, and multiple evaluation theory as the basis for setting up the higher education institution’s physical education teaching assessment system. Three first-level indexes comprise the entire index system, namely, “condition quality,” “process quality,” and “result quality.” Through fuzzy comprehensive evaluation, hierarchical analysis, and genetic algorithm, it is determined that the “process quality” is the most important factor. The “process quality” has the highest weight coefficient of 0.4419, which enhances the importance of the physical education teaching process in higher education institutions. After determining the evaluation index system, the average physical education scores of X physical education classes in University H were calculated by conventional teaching evaluation means and the evaluation means established in this paper, respectively, and compared and analyzed. The difference between the two final average scores was 2.9, which was attributed to the fact that the multivariate evaluation means paying more attention to the core literacy of students’ health. The standard deviation of the statistical results is 2.3, and the skewness, kurtosis, and S-W test values meet the statistical requirements and satisfy the normal distribution, which is thorough and scientific and can encourage academic institutions to pay more focus on how they teach and students’ fundamental physical literacy. These institutions can enhance their instruction by implementing the evaluation system established in this paper, which will improve the quality of instruction and learning in higher education sports.