Gait is a novel biometric feature that offers human identification at a distance and without physical interaction with the imaging device. Moreover, it performs well even in low resolution which makes it ideal for use in numerous human identification applications, e.g.,visual surveillance, monitoring and access control systems. Most existing gait-based human identification solutions extract human body silhouettes, contours or shapes from the images and construct gait features. Therefore, the performance of such algorithms highly depends upon the accuracy of human body segmentation, which is still a challenging problem in the literature. In this paper, we propose a new gait recognition algorithm which uses the spatial and temporal motion characteristics of human gait for individual identification without needing the silhouette extraction. The proposed algorithm extracts a set of spatiotemporal local descriptors from the gait video sequences. The extracted descriptors are encoded using the Fisher vector encoding and Gaussian mixture model-based codebook. The encoded features are classified using a simple linear support vector machine to recognize the individuals. The proposed gait recognition method is evaluated on five widely used gait databases, including indoor (CMU MoBo, CASIA-B) and outdoor (NLPR, CASIA-C, TUM GAID) gait databases. The results reveal that our method showed excellent performance on all five databases and outperformed the state-of-the-art gait recognition approaches.