Periodontal disease is inflammation of the gums and without good oral hygiene, it can progress to periodontitis. Oral hygiene might be related to a patient’s health literacy (HL), defined as ability to gain access, understand, and use information to promote and maintain good health. The aim of our study is to examine the associations of HL with indicators of periodontal disease. A cross-sectional study on 1117 adults (36.2% males; mean age = 36.4, SD = 14.2) attending dental hygiene treatment was conducted. Data on demographics, socioeconomic status, and nine domains of HL (Health Literacy Questionnaire, HLQ) were collected by questionnaire, and Community Periodontal Index of Treatment Needs (CPITN) was established by the dental hygienist. Data were analysed using t-tests and logistic regression. Respondents with periodontal disease (N = 152) had statistically significantly lower levels of HL in seven out of nine HLQ domains compared to intact patients (N = 818) (t from 3.03 to 4.75, p < 0.01). Association of higher HL in seven domains with lower chance of diagnosed periodontal disease remain significant even after adjustment for age, gender and educational attainment (adjusted ORs 0.55–0.67, p < 0.05). Our findings confirm that an individual’s lower HL is significantly associated with higher chance of periodontal disease incidence, specifically among Slovak adults attending oral hygiene clinics. HL might be a promising factor in the improvement of oral health in this population, worthy of consideration in intervention and preventive activities.