Health literacy is an indicator of a society’s ability to make better health judgements for themselves and the people around them. This study investigated the prevalence of health literacy among Malaysian adults and provided an overall picture of the society’s current health literacy status, which has not been previously assessed. The study also highlighted socio-demographic markers of communities with limited health literacy that may warrant future intervention. A population-based self-administered survey using the Health Literacy Survey Malaysian Questionnaire18 (HLS-M-Q18) instrument was conducted as part of the National Health Morbidity Survey 2019 in Malaysia. The nationwide survey utilized a two-staged stratified random sampling method. A sample of 9478 individuals aged 18 and above, drawn from the living quarter list, participated in the study. The health literacy score was divided into three levels; limited, sufficient, and excellent. Findings showed a majority of the Malaysian population had a sufficient health literacy level in all three domains—healthcare, diseases prevention and health promotion (49.1%, 44.2%, and 47.5%, respectively)—albeit leaning towards the lower end of the category with an average score of 35.5. The limited health literacy groups were prevalent among respondents with older age (68%), lower education level (64.8%), and lower household income (49.5%). The overall health literacy status for Malaysia was categorized at a lower sufficiency level. Future health literacy improvements should focus on communities with a limited health literacy level to improve the overall score.