Trellis-coding techniques are applied to continuous-phase frequency-shift keying (CPFSK). A new coding scheme based on convolutional codes on the ring of integers modulo-P is shown to be a natural way to apply trellis coding to CPFSK. Previous work has decomposed CPFSK into two parts: a linear encoder, with memory called the continuous phase encoder (CPE), and a memoryless modulator (MM), where the CPE often has a code structure defined over the ring of integers modulo-P. The combination of a modulo-P convolutional channel encoder (CE) and the CPE is a linear modulo-P encoder. Design examples are given for rate-1/2 coded quaternary CPFSK with modulation indexes 1/2 and 1/4, and rate-2/3 coded octal CPFSK with modulation index 1/8. Combinations are optimized in the normalized minimum Euclidean distance sense for a given total number of states in the overall MLSE receiver. Numerical results show that this new coding scheme consistently obtains better performance than previous schemes.>