In this paper, we address the almost sure stability problem of Caputo fractional-order Markovian switching nonlinear systems. Firstly, for the globally asymptotic stability almost surely (GAS a.s.) and exponential stability almost surely (ES a.s.) of Caputo fractional-order Markovian switching nonlinear systems (CFMNSs) with the constant lower bound initial time, some sufficient conditions are given by the stochastic Multi-Lyapunov function and probability analysis method. Then, for CFMNSs with the variable lower bound initial time, a resetting CFMNSs model is constructed to update synchronously the lower bound initial time and the corresponding initial state value of the above-mentioned system with the change of switching. After that, for CFMNSs with the variable lower bound initial time under the resetting means, the sufficient conditions of GAS a.s. and ES a.s. are given using the probability analysis method and stochastic Multi-Lyapunov function, respectively. Finally, numerical examples show that our results are effective.