Markov-switching dynamic stochastic general equilibrium (MSDSGE) modeling has become a growing body of literature on economic and policy issues related to structural shifts. This paper develops a general perturbation methodology for constructing high-order approximations to the solutions of MSDSGE models. Our new method—“the partition perturbation method”—partitions the Markov-switching parameter space to keep a maximum number of time-varying parameters from perturbation. For this method to work in practice, we show how to reduce the potentially intractable problem of solving MSDSGE models to the manageable problem of solving a system of quadratic polynomial equations. This approach allows us to first obtain all the solutions and then determine how many of them are stable. We illustrate the tractability of our methodology through two revealing examples.