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 (PM), nitrogen dioxide (NO), 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 PM, NO, 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 PM, NO, 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/m for PM, 12.6 ppb for NO, and 31.5 for AQI). In multi-pollutant models, the PM associations were almost independent from NO. However, the RRs for NO were slightly attenuated after adjustment for PM but they were still largely independent from PM. The cumulative relative risks (95% CI) per IQR increment reached maximum during the cooler months, including: 1.13 (1.06, 1.20) for PM at lag 0-31 (for females, all ages); 1.17 (1.10, 1.25) for NO 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 NO than PM 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 PM and NO in Iran.