State space models are a widely used tool in time series analysis to deal with processes which gradually change over time. Model specification however is a diffcult task as one has to decide which components to include in the model and to specify whether these are fixed or stochastic. In the Bayesian approach, model selection relies on the posterior probabilities of a model given the data. These can be determined for each model separately by using Bayes' rule, which requires estimation of the marginal likelihoods by some numerical methods. The modern approach to Bayesian model selection is to apply model space MCMC methods by sampling jointly model indicators and parameters, as e.g. in the stochastic variable selection approach (George and McCulloch, 1997), which is usually applied to model selection for regression models. In this talk we show that a stochastic model search MCMC method is feasible for Gaussian as well as non-Gaussian time series data (binary data, multinomial data, count data) that chooses appropriate components in a structural time series model and decides, if these components are deterministic or stochastic. For non-Gaussian state space models the stochastic model search MCMC methods makes use of auxiliary mixture sampling developed in Frühwirth-Schnatter and Wagner (2006) for count data and in Frühwirth- Schnatter and Frühwirth (2007) for binary and multinomial data.