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 study proposes a fully backward compatible novel method for bandwidth extension (BWE) of NB speech. The method uses integer wavelet transform technique to provide a perceptually better wideband (WB) speech signal. The spectral envelope parameters are extracted from the down sampled frequency shifted version of the high-frequency components of speech signal existing above NB, which are spread by using pseudo-noise codes, and are embedded in the integer wavelet coefficients of NB speech signal. The hearing threshold is calculated in the integer wavelet domain and this threshold is employed as the embedding threshold. The embedded information is extracted at the receiving end to reconstruct the WB speech signal. Theoretical and simulation analyses show that the proposed method is robust to quantisation and channel noises. The comparison category rating listening and log spectral distortion tests clearly show that the reconstructed WB signal gives a much better performance in terms of speech quality when compared with some of the existing speech BWE methods employing data hiding.