Human gait recognition has numerous challenges due to view angle changing, human dressing, bag carrying, and pedestrian walking speed, etc. In order to increase gait recognition accuracy under these circumstances, in this paper we propose a method for gait recognition based on a self-adaptive hidden Markov model (SAHMM). First, we present a feature extraction algorithm based on local gait energy image (LGEI) and construct an observation vector set. By using this set, we optimize parameters of the SAHMM-based method for gait recognition. Finally, the proposed method is evaluated extensively based on the CASIA Dataset B for gait recognition under various conditions such as cross view, human dressing, or bag carrying, etc. Furthermore, the generalization ability of this method is verified based on the OU-ISIR Large Population Dataset. Both experimental results show that the proposed method exhibits superior performance in comparison with those existing methods.