Background: The purpose of this study was to analyze which gait variables are the best for detecting cognitive impairment and to determine if age and gender can influence gait variations in older people. Methods: 65 participants took part in this study (22 men and 43 women; age: 73.88 ± 9.56 years). We use the Montreal Cognitive Assessment (MoCA) to assess mild cognitive impairment (MCI). Gait speed (GS) and the complex gait test (CGT) were analyzed with photocells Witty (Microgate, Italia). The OptoGait system (Microgate, Italia) was used to analyze step length (SL) and step coefficient of variation (CV sl). Results: There was a significant association between MoCA and SL (r = 0.420; p = 0.002), CV sl (r = −0.591; p < 0.001), and CGT (r = −0.406; p = 0.001). Instrumental activities of daily living showed significant association with SL (r = 0.563; p < 0.001); CV sl (r = −0.762; p < 0.001), CGT (r = −0.622; p < 0.001), and GS (r = 0.418; p < 0.001). CV sl showed the best results with MoCA when linear regression analysis was applied (R2 = 0.560; p = 0.007; Y = 23.669 − 0.320x). Participants older than 79 years showed lower MoCA scores and poorer gait parameters than people younger than 79 years. Conclusions: CV sl, SL, CGT, and GS make it possible to detect MCI in older people, especially when these variables are evaluated as a whole.