Purpose: To quantify the long-term health outcomes of relapsing multiple sclerosis (MS) patients taking natalizumab, with attention to the risk of developing progressive multifocal leukoencephalopathy (PML), a usually fatal disease associated with natalizumab. Methods: We created a Markov model to perform a risk-benefit analysis of natalizumab. We modeled its effects on reducing relapses and disease progression from a published natural history cohort and clinical trial results. Health changes were measured in quality-adjusted life-years (QALYs) and were based on patient health preferences for disability levels, relapses, and treatment side effects. For comparison, patient cohorts treated with no disease-modifying treatment, interferon beta-1a, and a theoretical “perfect” MS treatment were modeled. A discount rate of 3% was applied to future QALYs. Sensitivity analysis was used to explore model uncertainty, the impact of varying PML risk, and the negative impact of fear of PML. Results: The natural history cohort gained 8.70 QALYs over the base case 20-year time horizon. Treatment with natalizumab resulted in an additional 0.82 QALYs gained for a total of 9.52 QALYs. Treatment with interferon beta-1a resulted in an additional 0.42 QALYs gained for a total of 9.12 QALYs. The model was most sensitive to modulating relapse rate reductions for each treatment. Overall, natalizumab provided 43% of the theoretical QALY gain from a “perfect” MS treatment, while interferon beta-1a provided 22%. Because the health loss among the natalizumab treatment cohort due to developing PML was small (-0.06 QALYs), a 7-fold increase in the risk of PML was required for interferon beta-1a to become the preferred treatment. In addition, a very large disutility due to fear of developing PML was required for interferon beta-1a to become the preferred treatment. Conclusions: The benefits of long-term treatment with natalizumab far outweighed the risks of side effects and developing PML. However, large health gains remain untapped by present relapsing MS treatments. Model uncertainty may be reduced if longer-term studies and head-to-head comparisons between competing treatment strategies are conducted. More research is also needed to assess MS patients' willingness to accept uncertainty when facing a small, yet dreaded risk.