The independent and joint effects of within- and between-city contrasts in air pollution on mortality have been investigated rarely. To examine the differential effects of between- versus within-city contrasts in pollution exposure, we used both ambient measurements and land use regression models to assess associations with mortality and exposure to nitrogen dioxide (NO2) among ~735,600 adults in 10 of the largest Canadian cities. We estimated exposure contrasts partitioned into within- and between-city contrasts, and the sum of these as overall exposures, for every year from 1984 to 2006. Residential histories allowed us to follow subjects annually during the study period. We calculated hazard ratios (HRs) adjusted for many personal and contextual variables. In fully-adjusted, random-effects models, we found positive associations between overall NO2 exposures and mortality from non-accidental causes (HR per 5 p.p.b.: 1.05; 95% confidence interval (CI): 1.03-1.07), cardiovascular disease (HR per 5 p.p.b.: 1.04; 95% CI: 1.01-1.06), ischaemic heart disease (HR per 5 p.p.b.: 1.05; 95% CI: 1.02-1.08) and respiratory disease (HR per 5 p.p.b.: 1.04; 95% CI: 0.99-1.08), but not from cerebrovascular disease (HR per 5 p.p.b.: 1.01; 95% CI: 0.96-1.06). We found that most of these associations were determined by within-city contrasts, as opposed to by between-city contrasts in NO2. Our results suggest that variation in NO2 concentrations within a city may represent a more toxic mixture of pollution than variation between cities.