In this paper, we introduce hidden Markov model (HMM) based packet loss concealment (PLC) methods and discuss the impact of Markovian assumptions on the performance of these models. We also present a new PLC method, implemented on the G.722.2 codec, which relies on the HMM and Decision Tree (DT), namely HMDT architecture, to enhance the perceptual quality of Voice over Internet Protocol (VoIP) communications under severe packet loss conditions. The proposed method is a receiver-based model that tracks the statistical evolution of speech signals through HMM and uses the DT architecture to predict/estimate accurately the lost speech packets by exploiting the surrounding received speech packets. Objective and subjective metrics are used to evaluate the performance of the proposed method. Test results show that our proposed method enhances considerably the speech quality of the reconstructed speech signal and produces a more natural speech variation compared to conventional PLC methods.