The pricing problem for American options in Markov-modulated Levy models is solved. The early exercise boundaries and prices are calculated using a generalization of Carr's randomization procedure for regime-switching models. The pricing procedure is efficient even if the number of states is large, provided the transition rates are not large w.r.t. the riskless rates. The payoffs and riskless rates may depend on a state. Special cases are stochastic volatility models and models with stochastic interest rate; both must be modeled as finite-state Markov chains.