Long-term exposure to air pollution is associated with age-related diseases. We explored the association between accelerated biological aging and air pollution, a potential mechanism linking air pollution and health. We estimated long-term exposure to PM10, PM2.5, PM2.5 absorbance/black carbon (BC), and NOx via land-use regression models in individuals from the KORA F4 cohort. Accelerated biological aging was assessed using telomere length (TeloAA) and three epigenetic measures: DNA methylation age acceleration (DNAmAA), extrinsic epigenetic age acceleration (correlated with immune cell counts, EEAA), and intrinsic epigenetic age acceleration (independent of immune cell counts, IEAA). We also investigated sex-specific associations between air pollution and biological aging, given the published association between sex and aging measures. In KORA an interquartile range (0.97 µg/m3) increase in PM2.5 was associated with a 0.33 y increase in EEAA (CI = 0.01, 0.64; P = 0.04). BC and NOx (indicators or traffic exposure) were associated with DNAmAA and IEAA in women, while TeloAA was inversely associated with BC in men. We replicated this inverse BC-TeloAA association in the Normative Aging Study, a male cohort based in the USA. A multiple phenotype analysis in KORA F4 combining all aging measures showed that BC and PM10 were broadly associated with biological aging in men. Thus, we conclude that long-term exposure to air pollution is associated with biological aging measures, potentially in a sex-specific manner. However, many of the associations were relatively weak and further replication of overall and sex-specific associations is warranted.