We propose a new technique using adaptive hierarchical modulation for simultaneous voice and multi-class data transmission over fading channels. We present closed-form expressions as well as numerical results for outage probability and achievable spectral efficiency for voice and data transmissions over Nakagami-m fading channels. We also extend the adaptive techniques employing hybrid binary shift keying (BPSK)/M-ary amplitude modulation (M-AM)  and uniform M-my quadrature amplitude modulation (M-QAM)  for simultaneous voice and two different classes of data transmission. Compared to the extended schemes, the proposed new scheme is spectrally more efficient for data transmission while keeping the same outage probabilities for voice and data (both classes) as the scheme employing BPSKM-AM. The new scheme provides also as a byproduct a spectrally more efficient way of transmitting voice and single ciass data than the schemes proposed in  and .