Public telephone systems transmit speech across a limited frequency range, about 300 –3400 Hz, called narrowband (NB) which results in a significant reduction of quality and intelligibility of speech. This paper proposes a fully backward compatible novel method for bandwidth extension of NB speech. The method uses adaptive data hiding technique to provide a perceptually better wideband speech signal. The spectral envelope parameters are extracted from the high frequency components of speech signal existing above NB, which are then spread by using spreading sequences, and are embedded in the NB speech signal using adaptive data hiding technique. The embedded information is extracted at the receiving end to reconstruct the wideband speech signal. Theoretical and simulation analyses show that the proposed method is robust to quantization and channel noises. The log spectral distortion test clearly show that the reconstructed wideband signal gives a much better performance in terms of speech quality when compared to the conventional speech bandwidth extension methods employing data hiding.