Background: The promotion of health literacy is seen as an urgent goal in public health and education and, hence, should be integrated in the school context as a component of the holistic health promoting school (HPS) approach. However, only limited empirical studies have addressed health literacy of school staff so far. Hence, this study aimed to examine the level of health literacy among school leaders and its association with the extent of HPS implementation. Methods: A cross-sectional study with n = 680 school principals and members of the school management board from Germany was carried out at the end of 2018. Individual health literacy, attitudes, and competencies towards HPS and occupational self-efficacy served as independent variables and the level of HPS implementation was the dependent variable. Data were analyzed using univariate and bivariate analysis as well as multiple binary logistic regression. Results: 29.3% of school leaders show a limited health literacy with significantly higher values found for male respondents. Regression analyses revealed that male gender (OR: 1.91, 95% CI: 1.22–2.99), HPS attitudes (OR: 3.17, 95% CI: 2.13–4.72), and HPS competencies (OR: 3.66, 95% CI: 2.43–5.50) were associated with a lower level of HPS implementation. Furthermore, regression analyses differentiated by gender showed that limited health literacy is associated with a low level of HPS implementation for male school leaders only (OR: 2.81, 95% CI: 1.22–6.45). Conclusions: The promotion of health literacy especially for male leaders would not only result in positive effects on an individual level but also could contribute to a stronger implementation of activities on school health promotion. We suggest integrating health literacy, HPS attitudes, and competencies more strongly into the qualification and in further training of school leaders.