Background: The success of a clinical trial is often dependant on whether recruitment targets can be met in the required time frame. Despite an increase in research into the benefits of exercise in people with multiple sclerosis (PwMS), no trial has reported detailed data on effective recruitment strategies for large-scale randomised controlled trials. The main purpose of this report is to provide a detailed outline of recruitment strategies, rates and estimated costs in the Exercise Intervention for Multiple Sclerosis (ExIMS) trial to identify best practices for future trials involving multiple sclerosis (MS) patient recruitment. Methods: The ExIMS researchers recruited 120 PwMS to participate in a 12-week exercise intervention. Participants were randomly allocated to either exercise or usual-care control groups. Participants were sedentary, aged 18–65 years and had Expanded Disability Status Scale scores of 1.0–6.5. Recruitment strategies included attendance at MS outpatient clinics, consultant mail-out and trial awareness-raising activities. Results: A total of 120 participants were recruited over the course of 34 months. To achieve this target, 369 potentially eligible and interested participants were identified. A total of 60 % of participants were recruited via MS clinics, 29.2 % from consultant mail-outs and 10.8 % through trial awareness. The randomisation yields were 33.2 %, 31.0 % and 68.4 % for MS clinic, consultant mail-outs and trial awareness strategies, respectively. The main reason for ineligibility was being too active (69.2 %), whilst for eligible participants the most common reason for non-participation was the need to travel to the study site (15.8 %). Recruitment via consultant mail out was the most cost-effective strategy, with MS clinics being the most time-consuming and most costly. Conclusions: To reach recruitment targets in a timely fashion, a variety of methods were employed. Although consultant mail-outs were the most cost-effective recruitment strategy, use of this method alone would not have allowed us to obtain the predetermined number of participants in the required time period, thus leading to costly extensions of the project or failure to reach the number of participants required for sufficient statistical power. Thus, a multifaceted approach to recruitment is recommended for future trials.