In this paper, we study the optimal placement of market orders in a limit order book (LOB) market when the market resilience rate, which is the rate at which market replenishes itself after each trade, is stochastic. More specifically, we establish a tractable extension to the optimal execution model in Obizhaeva and Wang (2013) by modelling the dynamics of the resilience rate to be driven by a Markov chain. When the LOB replenishes itself stochastically through time, the optimal execution strategy becomes state-dependent, and is driven linearly by the current remaining position and the current temporary price impact, with their linear dependence based on the expectation of the dynamics of future resilience rate. A trader would optimally place more aggressive (respectively, conservative) market orders when the limit order book switches from a low to a high resilience state, (respectively, from a high to a low resilience state). Our cost saving analysis indicates that the incremental execution costs can be substantial when the agent ignores the stochastic dynamics of the market resilience rate by adopting the state-independent strategies.