This paper investigates the code search problem for trellis-coded multidimensional phase modulation for Rayleigh fading channels. New set partitionings for multiple phase-shift keying (M-PSK) are proposed using the effective code length (ECL) and the minimum product distance (PD) as the code design criteria. By using these set-partitionings rules, new multidimensional codes which are optimum for Rayleigh fading channels are constructed. The proposed codes compare favorably with the existing multidimensional trellis codes on fading channels in terms of bit error performance. The bit error performance is evaluated by simulation.