To better describe the time-varying property of the dynamic investment risk and the ambiguity of the random return process, we propose two multi-period robust risk measures under the regime switching framework. Using regime-dependent dynamic uncertainty sets, we show that the multi-period robust portfolio selection problems under the two multi-period robust risk measures with regime switching can be transformed into second order cone programs, which can thus be efficiently solved in polynomial time. To show the generality of the dynamic uncertainty sets under the regime switching framework, we further consider multi-period robust risk measures under time-varying uncertainty sets with moments uncertainty and discuss the tractability of the corresponding multi-period robust portfolio selection problems. A series of empirical results demonstrate that the robust portfolio selection models with regime switching can flexibly help the investor make superior and robust investment strategies according to the switching of the market environment.