Mobility impairment is a hallmark of disease worsening in multiple sclerosis (MS), yet its phenotypic diversity and pathophysiology mechanisms are not completely understood. Conventional gait assessments often rely on subjective clinical measures, which may not fully capture the complexity of gait abnormalities. The integration of advanced quantitative gait analysis, quantitative from MRI, and machine learning (ML) may reveal unique mobility phenotypes, potentially reflecting underlying disease mechanisms and heterogeneity. In this study, we aimed to identify and characterize mobility phenotypes among people with MS (pwMS) using a mixed approach with spatiotemporal gait parameters and MRI-derived features, supported by unsupervised ML clustering. 1026 pwMS underwent comprehensive gait assessments and quantitative MRI between 2018 and 2023. Principal component analysis was applied for dimensionality reduction and k-means clustering to identify distinct phenotypes. Clusters were compared using demographic, clinical, and MRI features, with statistical comparisons performed using Kruskal-Wallis and Chi-square tests. Four gait clusters were identified. Cluster 1 (faster stable, 47.8%), demonstrated the most efficient gait features and highest grey matter fractions. Cluster 4 (slow severely unstable, 7.4%) showed profound disability, shortest strides, lowest velocity, and greatest variability. Intermediate clusters 2 (slower stable, 32.3%) and 3 (moderately unstable, 12.6%) had similar velocity but differed in cadence and stride length. Cluster 3, marked by shorter steps and increased cadence, showed higher lesion burden and lower brain parenchymal fraction, suggesting emerging structural impairment and possible compensatory gait. Clinical measures aligned with these findings: unstable Clusters 3 and 4 had the highest proportion of progressive MS, worst disability scores, longest disease duration, and greatest self-reported gait impairment. Integrating quantitative MRI metrics with spatiotemporal gait analysis has the potential to phenotype clinical impairments in pwMS. ML-driven analysis identified a novel intermediate cluster, distinguished by a gait with increased cadence and shorter strides, alongside distinct MRI abnormalities. This pattern may reflect a potential adaptation within the mobility spectrum, not yet conclusively discernible by human raters but detectable through ML.