Long-term memory (LTM) is one of the diverse cognitive functions adversely affected by multiple sclerosis (MS). The LTM deficits have often been attributed to failure of retrieval, whereas encoding processes are presumed intact. However, support for this view comes primarily from studies in which encoding and retrieval operations were not investigated systematically. In the current study, we used an encoding specificity paradigm to examine the robustness of encoding in MS and to specifically evaluate the impact of the disease on contextual memory. We hypothesized that persons with MS would exhibit a selective impairment in retrieving items from LTM when required to generate new cue-target associations at encoding, but not when cues held a strong preexisting relationship to the targets. The findings supported the hypotheses. We conclude that the mnemonic deficits associated with MS affect both encoding and retrieval. Specifically, problems with binding of contextual information at encoding impair effective retrieval of memories. Nonetheless, access to these memories can be gained through preexisting associations organized in the semantic network.