The diversity order is crucial for the performance of communication systems over Fading Channels. It has been shown by Zehavi that the diversity and hence performance of coded modulation over fading channels can be improved by bitwise interleaving at the encoder output, and by using an appropriate soft decision metric as an input to the Viterbi decoder. A related approach is co-ordinate interleaving whereby the signal space co-ordinates are interleaved before transmission. In this paper we combine both bit interleaving and co-ordinate interleaving to increase the diversity order. The resulting system is referred here as Bit and Co-ordinate Interleaved Coded Modulation (BCICM). The pairwise probability of error is also derived, which shows that by proper design the diversity order can be doubled over Bit Interleaved Coded Modulation (BICM), for two dimensional signal sets. Simulation results for rate 2/3, 4-state 8-PSK coded modulation schemes show that BCICM significantly outperforms all known coded modulation (symbol or bit interleaved) schemes.