The performance of uncoded phase-shift-keying (PSK) and quadrature amplitude modulation (QAM) schemes over fading channels can be improved by using coded gain coupled with interleaving and depends on the comlexity of the code. Recently, it was shown that constellation rotation coupled with interleaving can be used to improve the performance of QPSK modulation over block-fading single-input-single-output (SISO) wireless communication channels. This paper considers the use of such a scheme with higher order constellation sets such as 8PSK and 16QAM. A framework is then presented for the calculation of the optimum rotation angle for MPSK/MQAM schemes. A simple cost function based on the union bound of the symbol error probability (SEP) is defined. The optimum rotation angle is then found by minimizing the cost function using the gradient search algorithm. The obtained simulation results show considerable improvement over the conventional unrotated system.@en