There is limited evidence for short-term association between mortality and ambient air pollution in the Middle East and no study has evaluated exposure windows of about a month prior to death. We investigated all-cause non-accidental daily mortality and its association with fine particulate matter (PM2.5), nitrogen dioxide (NO2), and the Air Quality Index (AQI) from March 2011 through March 2014 in the megacity of Tehran, Iran. Generalized additive quasi-Poisson models were used within a distributed lag linear modeling framework to estimate the cumulative effects of PM2.5, NO2, and the AQI up to a lag of 45 days. We further conducted multi-pollutant models and also stratified the analyses by sex, age group, and season. The relative risk (95% confidence interval (CI)) for all seasons, both sexes and all ages at lag 0 for PM2.5, NO2, and AQI were 1.004 (1.001, 1.007), 1.003 (0.999, 1.007), and 1.004 (1.001, 1.007), respectively, per inter-quartile range (IQR) increment (18.8 μg/m3 for PM2.5, 12.6 ppb for NO2, and 31.5 for AQI). In multi-pollutant models, the PM2.5 associations were almost independent from NO2. However, the RRs for NO2 were slightly attenuated after adjustment for PM2.5 but they were still largely independent from PM2.5. The cumulative relative risks (95% CI) per IQR increment reached maximum during the cooler months, including: 1.13 (1.06, 1.20) for PM2.5 at lag 0-31 (for females, all ages); 1.17 (1.10, 1.25) for NO2 at lag 0-45 (for males, all ages); and 1.13 (1.07, 1.20) for the AQI at lag 0-30 (for females, all ages). Generally, the RRs were slightly larger for NO2 than PM2.5 and AQI. We found somewhat larger RRs in females, age group >65 years of age, and in cooler months. In summary, positive associations were found in most models. This is the first study to report short-term associations between all-cause non-accidental mortality and ambient PM2.5 and NO2 in Iran.