Higher air pollution exposure and shorter leukocyte telomere length (LTL) are both associated with increased risk of coronary heart disease (CHD), and share plausible mechanisms, including inflammation. LTL may serve as a biomarker of air pollution exposure and may be intervened with to reduce the risk of CHD. To the best of our knowledge, we are the first to test the mediation effect of LTL in the relationship between air pollution exposure and incident CHD. Using the UK Biobank (UKB) data (n = 317,601), we conducted a prospective study linking residential air pollution exposure (PM2.5, PM10, NO2, NOx) and LTL to incident CHD during a mean follow-up of 12.6 years. Cox proportional hazards models and generalized additive models with penalized spline functions were used to model the associations of pollutant concentrations and LTL with incident CHD. We found non-linear associations of air pollution exposure with LTL and CHD. Pollutant concentrations in the lower range were decreasingly associated with longer LTL and reduced risk of CHD. The associations between lower pollutant concentrations and reduced risk of CHD, however, were minimally mediated by LTL (<3%). Our findings suggest that air pollution influences CHD through pathways that do not involve LTL. Replication is needed with improved measurements of air pollution that more accurately assesses personal exposure.