Background: Although epidemiological studies have reported associations between mortality and both ambient air pollution and air temperature, it remains uncertain whether the mortality effects of air pollution are modified by temperature and vice versa. Moreover, little is known on the interactions between ultrafine particles (diameter ≤ 100 nm, UFP) and temperature. Objective: We investigated whether the short-term associations of particle number concentration (PNC in the ultrafine range (≤100 nm) or total PNC ≤ 3000 nm, as a proxy for UFP), particulate matter ≤ 2.5 μm (PM2.5) and ≤ 10 μm (PM10), and ozone with daily total natural and cardiovascular mortality were modified by air temperature and whether air pollution levels affected the temperature-mortality associations in eight European urban areas during 1999–2013. Methods: We first analyzed air temperature-stratified associations between air pollution and total natural (nonaccidental) and cardiovascular mortality as well as air pollution-stratified temperature-mortality associations using city-specific over-dispersed Poisson additive models with a distributed lag nonlinear temperature term in each city. All models were adjusted for long-term and seasonal trend, day of the week, influenza epidemics, and population dynamics due to summer vacation and holidays. City-specific effect estimates were then pooled using random-effects meta-analysis. Results: Pooled associations between air pollutants and total and cardiovascular mortality were overall positive and generally stronger at high relatively compared to low air temperatures. For example, on days with high air temperatures (>75th percentile), an increase of 10,000 particles/cm3 in PNC corresponded to a 2.51% (95% CI: 0.39%, 4.67%) increase in cardiovascular mortality, which was significantly higher than that on days with low air temperatures (<25th percentile) [−0.18% (95% CI: −0.97%, 0.62%)]. On days with high air pollution (>50th percentile), both heat- and cold-related mortality risks increased. Conclusion: Our findings showed that high temperature could modify the effects of air pollution on daily mortality and high air pollution might enhance the air temperature effects.