This paper introduces an enhanced MSM (Mutual Subspace Method) methodology for gait recognition, to provide robustness to variations in walking speed. The enhanced MSM (eMSM) methodology expands and adapts the MSM, commonly used for face recognition, which is a static/physiological biometric, to gait recognition, which is a dynamic/behavioral biometrics. To address the loss of accuracy during calculation of the covariance matrix in the PCA step of MSM, we use a 2D PCA-based mutual subspace. Furhtermore, to enhance the discrimination capability, we rotate images over a number of angles, which enables us to extract richer gait features to then be fused by a boosting method. The eMSM methodology is evaluated on existing data sets which provide variable walking speed, i.e. CASIA-C and OU-ISIR gait databases, and it is shown to outperform state-of-the art methods. While the enhancement to MSM discussed in this paper uses combinations of 2D-PCA, rotation, boosting, other combinations of operations may also be advantageous.