Channels that are time-varying due to fading, interference, or variable noise can be modeled as finite-state Markov chains. These channels have memory due to correlated variations, which should be incorporated into the design of an optimal code. However, optimal codes of this type are difficult to design, and the complexity of their decoding algorithms grows exponentially with memory length. Thus, memoryless codes are typically used and the encoded bit stream is interleaved prior to transmission to remove the effect of memory. This results in a performance loss relative to the inherent channel capacity . In this paper, we develop a decision-feedback decoding algorithm that uses the channel's Markovian structure to determine the maximum-likelihood input sequence. We show that this decoding scheme can achieve data rates approaching the Shannon limit with a moderate complexity increase over the conventional approach. We also present numerical results for the capacity and cutoff rate of a two-state fading channel with 4PSK modulation using both the decision-feedback decoder and the conventional memoryless encoding method.