In this paper we introduce and implement new techniques to investigate threshold effects in air pollution-mortality relationships. Our key interest is in measuring the dose-response relationship above and below a given threshold level where we allow for a large number of potential explanatory variables to trigger the threshold effect. This is in contrast to existing approaches that usually focus on a single threshold trigger. We allow for a myriad of threshold effects within a Bayesian statistical framework that accounts for model uncertainty (i.e. uncertainty about which threshold trigger and explanatory variables are appropriate). We apply these techniques in an empirical exercise using daily data from Toronto for 1992-1997. We investigate the existence and nature of threshold effects in the relationship between mortality and ozone (O3), total particulate matter (PM) and an index of other conventionally occurring air pollutants. In general, we find the effects of our considered pollutants on mortality to be statistically indistinguishable from zero with no evidence of thresholds. The one exception is ozone, for which results present an ambiguous picture. Ozone has no significant effect on mortality when we exclude threshold effects from the analysis. Allowing for thresholds we find a positive and significant effect for this pollutant when the threshold trigger is the average change in ozone two days ago. However, this significant effect is not observed after controlling for PM.