In this paper we aim to improve existing empirical exchange rate models by accounting for uncertainty with respect to the underlying structural representation. Within a flexible Bayesian non-linear time series framework, our modeling approach assumes that different regimes are characterized by commonly used structural exchange rate models, with their evolution being driven by a Markov process. We assume a time-varying transition probability matrix with transition probabilities depending on a measure of the monetary policy stance of the central bank at the home and foreign country. We apply this model to a set of eight exchange rates against the US dollar. In a forecasting exercise, we show that model evidence varies over time and a model approach that takes this empirical evidence seriously yields improvements in accuracy of density forecasts for most currency pairs considered.