In this paper we study constrained stochastic optimal control problems for Markovian switching systems, an extension of Markovian jump linear systems (MILS), where the subsystems are allowed to be nonlinear. We develop appropriate notions of invariance and stability for such systems and provide terminal conditions for stochastic model predictive control (SMPC) that guarantee mean-square stability and robust constraint fulfillment of the Markovian switching system in closed-loop with the SMPC law under very weak assumptions. In the special but important case of constrained MILS we present an algorithm for computing explicitly the SMPC control law off-line, that combines dynamic programming with parametric piecewise quadratic optimization. (C) 2014 Elsevier Ltd. All rights reserved.