© 2015 IEEE. Contemporary wireless networks are tasked with supporting different connection profiles, including real-time traffic and delay-sensitive communications. This creates a need to better understand the fundamental limits of forward error correction in non-asymptotic regimes. This paper characterizes the performance of block codes over finite-state channels and evaluates their queueing performance under maximum-likelihood decoding. Classical results from digital communications are revisited in the context of channels with rare transitions, and bounds on the probabilities of decoding failure are derived for random codes. This creates an analysis framework where channel dependencies within and across codewords are preserved. These results are subsequently integrated into a queueing problem formulation.