We present an optimal Adaptive Modulation and Coding (AMC) policy that minimizes the transmission latency and modulation/coding switching cost across a finite-state Markovian fading channel. We formulate the optimal tradeoff between the transmission latency and the modulation/coding switching cost as a stochastic shortest path Markov decision problem (MDP). By exploiting special structures of the formulated MDP and under certain sufficient conditions, we show that optimal modulation and coding selection policies are monotone in the state variables. These monotone optimal policies are computationally inexpensive to implement and are scalable in terms of channel and switching cost parameters. Numerical results confirm the monotonicity and threshold-based structure of the optimal MCS selection policies under the proposed sufficient conditions.