The reliable extraction of characteristic gait features from image sequences and their recognition are two important issues in gait recognition. In this paper, we propose a novel 2-step, model-based approach to gait recognition by employing a 5-link biped locomotion human model. We first extract the gait features from image sequences using the Metropolis-Hasting method. Hidden Markov Models are then trained based on the frequencies of these feature trajectories, from which recognition is performed. As it is entirely based on human gait, our approach is robust to different type of clothes the subjects wear. The model-based gait feature extraction step is insensitive to noise, cluttered background or even moving background. Furthermore, this approach also minimizes the size of the data required for recognition compared to model-free algorithms. We applied our method to both the USF Gait Challenge data-set and CMU MoBo data-set, and achieved recognition rate of 61% and 96%, respectively. The results suggest that the recognition rate is significantly limited by the distance of the subject to the camera.