To date, modems for use on fading land mobile satellite (MSAT) channel, which employ coherent detection and interleaving, have used forms of phase shift keying (PSK) for the modulation scheme. The objective of this paper is to present a receiver that utilizes trellis coded continuous phase frequency shift keying (CPFSK) with coherent detection and convolutional interleaving of the coded symbols. An earlier study considered trellis coded CPFSK with differential detection where decoding is based solely on the code trellis. A new decoding algorithm that copes with the interleaving is presented and uses information from both the modulation trellis and the code trellis. The performance results are obtained by Monte Carlo simulation and are partially verified through analysis. The fading model is Rician, but the line-of-sight (LOS) component is subjected to a log-normal transformation that represents attenuations due to foliage, which is referred to as shadowing. The main application for the receiver is to data transmission which requires a low bit error rate (BER) and has relaxed delay constraints relative to digital speech transmission. The system studied in not suitable for digital speech applications as the required interleaving depths lead to an unacceptable time delay.