This paper proposes a scheme of real-time secure communication system based on information hiding and speech recognition. The algorithm uses speech recognition to reduce the bit-rate of secret speech greatly. Then we design an information hiding algorithm by adaptively choosing embedding locations and adopting the multi-nary modulation technique. Experimental results show that this algorithm has good imperceptibility and robustness against various interference (A-law/U-law compression, low-pass filtering, white noise, etc) when the speech is transmitted over the public switching telephone network (PSTN). This algorithm can be widely used in secure voice communication and fax systems.