Background: Air pollutants can influence local and systemic inflammation, oxidative stress and microbiome composition. Therefore, air pollution may potentially represent an unexplored modifiable risk indicator for periodontitis. The aim of the current cross-sectional study was to investigate the epidemiological association between outdoor air pollution and periodontitis in a representative sample of the South Korean population. Methods: A total of 42,020 individuals, which were representative of 35.2 million South Koreans, were examined. The mean annual levels of particulate matter of 10 μm (PM10), ozone, sulfur dioxide (SO2), nitrogen dioxide (NO2) and humidity, were studied. Periodontitis was defined according to the Community Periodontal Index (CPI ≥ 3). Simple and multiple regression analyses using four different models were applied. Results: Every 5-μg/m3 increase in PM10 (OR = 1.17; 95% confidence interval—CI: 1.11–1.24) and of 0.005 ppm in ozone levels (OR = 1.4; 95% CI: 1.00–1.30) were positively associated with periodontitis prevalence. Conversely, every 5% increase in humidity (OR = 0.94; 95% CI: 0.90–0.99) and 0.003 ppm increase in NO2 levels (OR = 0.93; 95% CI: 0.89–0.96) were inversely associated with periodontitis occurrence. Conclusions: In this nationally representative population several air pollutants were found to be associated with periodontitis occurrence. Hence, the present results suggest that air pollution may be a new modifiable risk indicator for periodontitis.