Leukemia and lymphoma are the two most common forms of hematologic malignancy, and their etiology is largely unknown. Pathophysiological mechanisms suggest a possible association with air pollution, but little empirical evidence is available. We aimed to investigate the association between long-term residential exposure to outdoor air pollution and risk of leukemia and lymphoma. We pooled data from four cohorts from three European countries as part of the “Effects of Low-level Air Pollution: a Study in Europe” (ELAPSE) collaboration. We used Europe-wide land use regression models to assess annual mean concentrations of fine particulate matter (PM2.5), nitrogen dioxide (NO2), black carbon (BC) and ozone (O3) at residences. We also estimated concentrations of PM2.5 elemental components: copper (Cu), iron (Fe), zinc (Zn); sulfur (S); nickel (Ni), vanadium (V), silicon (Si) and potassium (K). We applied Cox proportional hazards models to investigate the associations. Among the study population of 247,436 individuals, 760 leukemia and 1122 lymphoma cases were diagnosed during 4,656,140 person-years of follow-up. The results showed a leukemia hazard ratio (HR) of 1.13 (95% confidence intervals [CI]: 1.01–1.26) per 10 μg/m3 NO2, which was robust in two-pollutant models and consistent across the four cohorts and according to smoking status. Sex-specific analyses suggested that this association was confined to the male population. Further, the results showed increased lymphoma HRs for PM2.5 (HR = 1.16; 95% CI: 1.02–1.34) and potassium content of PM2.5, which were consistent in two-pollutant models and according to sex. Our results suggest that air pollution at the residence may be associated with adult leukemia and lymphoma.