Objective: Processing speed (PS) deficits are the most common cognitive deficits in multiple sclerosis (MS), followed by learning and memory deficits, and are often an early cognitive problem. It has been argued that impaired PS is a primary consequence of MS, which in turn decreases learning. The current analysis examined the association between PS and learning in a large cohort of individuals with progressive MS. Methods: Baseline data from a randomized clinical trial on rehabilitation taking place at 11 centers across North America and Europe were analyzed. Participants included 275 individuals with clinically definite progressive MS (primary, secondary) consented into the trial. Results: Symbol Digit Modalities Test (SDMT) significantly correlated with California Verbal Learning Test-II (CVLT-II) ( r = 0.21, p = 0.0003) and Brief Visuospatial Memory Test–Revised (BVMT-R) ( r = 0.516, p < 0.0001). Receiver operating characteristic (ROC) analysis of the SDMT z score to distinguish between impaired and non-impaired CVLT-II performance demonstrated an area under the curve (AUC) of 0.61 (95% confidence interval (CI): 0.55–0.68) and a threshold of −1.62. ROC analysis between SDMT and BVMT-R resulted in an AUC of 0.77 (95% CI: 0.71–0.83) and threshold of −1.75 for the SDMT z score to predict impaired BVMT-R. Conclusion: Results indicate little ability beyond chance to predict CVLT-II from SDMT (61%), albeit statistically significant. In contrast, there was a 77% chance that the model could distinguish between impaired and non-impaired BVMT-R. Several potential explanations are discussed.