The aim of the study was to analyze lexical access strategies in patients with multiple sclerosis (MS) and their changes over time. We studied lexical access strategies during semantic and phonemic verbal fluency tests and also confrontation naming in a 2-year prospective cohort of 45 MS patients and 20 healthy controls. At baseline, switching lexical access strategy (both in semantic and in phonemic verbal fluency tests) and confrontation naming were significantly impaired in MS patients compared with controls. After 2 years follow-up, switching score decreased, and cluster size increased over time in semantic verbal fluency tasks, suggesting a failure in the retrieval of lexical information rather than an impairment of the lexical pool. In conclusion, these findings underline the significant presence of lexical access problems in patients with MS and could point out their key role in the alterations of high-level communications abilities in MS.