In this paper, we introduce multilevel coded continuous-phase frequency-shift keying (CPFSK) systems for both additive white Gaussian noise and fading channels based on multilevel coding and multistage decoding techniques. These schemes are designed under the constraint M greater than or equal to 2P for M-ary CPFSK with modulation index J/P. In order to maintain the phase continuity property after multilevel coding, we use some specific set partitioning rules. We construct examples to show that the proposed systems outperform the corresponding conventional one-level schemes. For the fading case, we consider an ideal fading channel where adjacent fading symbols are assumed to be independent and a correlated fading channel where bit interleavers are needed at each coding level. The computer simulation results show that the proposed systems have bit-error performance and decoder complexity advantages over the corresponding reference codes taken from the literature. It is also shown that there is only a slight degradation on the bit error performance for correlated fading, compared to the ideal fading case.