The increasing burden of lung cancer (LC) in Crete, Greece, has raised certain concerns about the potential association of environmental risk factors with LC. The aim of this study was to assess outdoor air pollution (OAP) and the risk for LC mortality for the first time in Crete using LC primary data. 5057 LC cases (diagnosed from 1992 to 2013) were obtained from the Cancer Registry of Crete (http://www.crc.uoc.gr) and followed up until 2014. The age-standardized incidence and mortality rates (ASIR) were calculated. Data on OAP indicators [particulate matter (PM)2.5, between 2.5 and 10 μm (PM2.5–10), PM10, PM2.5 absorbance (black carbon measure), nitrogen dioxide (NO2), and nitrogen oxides (NOx)] were collected. Spatial statistics were calculated and the binary logistic regression model was constructed at α=0.05 in IBM SPSS 24 and ArcMap 10.3.1. LC in Crete accounts for 40.2 new cases/100 000/year for both sexes (ASIRmales=73.1 new cases/100 000/year; ASIRfemales=11.8 new cases/100 000/year). Annual median estimates of environmental concentrations in Crete were as follows: PM2.5=20.7 (±1.5) µg/m3, PM10=38.9 (±2.5) µg/m3, PM2.5–10=59.6 (±3.7) µg/m3, PM2.5 absorbance=1.2 (±0.3)×10−5/m, NO2=15.2 (±3.8) µg/m3, and NOx=20.1 (±4.9) µg/m3. A statistically significant association was observed between OAP and LC mortality (mean correlation coefficient=0.75; P<0.05). The highest risk for 5-year LC mortality was found in the major urban centers and several south-east and north-west rural regions of Crete (relative risk=3.2, 95% confidence interval=1.6–4.7). OAP seems to be an important determinant of LC mortality. Targeted interventions should be performed in the high-risk areas.