Many research studies have demonstrated that gait can serve as a useful biometric modality for human identification at a distance. Traditional gait recognition systems, however, have mostly been evaluated without explicitly considering the most relevant gait features, which might have compromised performance. We investigate the problem of selecting a subset of the most relevant gait features for improving gait recognition performance. This is achieved by discarding redundant and irrelevant gait features while preserving the most informative ones. Motivated by our previous work on feature subset selection using genetic algorithms (GAs), we propose using GAs to select an optimal subset of gait features. First, features are extracted using kernel principal component analysis (KPCA) on spatiotemporal projections of gait silhouettes. Then, GA is applied to select a subset of eigenvectors in KPCA space that best represents a subject’s identity. Each gait pattern is then represented by projecting it only on the eigenvectors selected by the GA. To evaluate the effectiveness of the selected features, we have experimented with two different classifiers: nearest-neighbor and Naïve Bayes classifier. We report considerable gait recognition performance improvements on the Georgia Tech and CASIA databases.