Background: Natalizumab is a widely used high-efficacy treatment in multiple sclerosis (MS). Real-world evidence regarding long-term effectiveness and safety is warranted. We performed a nationwide study evaluating prescription patterns, effectiveness, and adverse events. Methods: A nationwide cohort study using the Danish MS Registry. Patients initiating natalizumab between June 2006 and April 2020 were included. Patient characteristics, annualized relapse rates (ARRs), confirmed Expanded Disability Status Scale (EDSS) score worsening, MRI activity (new/enlarging T2- or gadolinium-enhancing lesions), and reported adverse events were evaluated. Further, prescription patterns and outcomes across different time periods (“epochs”) were analysed. Results: In total, 2424 patients were enrolled, with a median follow-up time of 2.7 years (interquartile range (IQR) 1.2–5.1). In recent epochs, patients were younger, had lower EDSS scores, had fewer pre-treatment relapses and were more often treatment naïve. At 13 years of follow-up, 36% had a confirmed EDSS worsening. On-treatment ARR was 0.30, corresponding to a 72% reduction from pre-initiation. MRI activity was rare, 6.8% had activity within 2–14 months from treatment start, 3.4% within 14–26 months, and 2.7% within 26–38 months. Approximately 14% of patients reported adverse events, with cephalalgia constituting the majority. During the study, 62.3% discontinued treatment. Of these, the main cause (41%) was due to JCV antibodies, while discontinuations due to disease activity (9%) or adverse events (9%) were less frequent. Conclusion: Natalizumab is increasingly used earlier in the disease course. Most patients treated with natalizumab are clinically stable with few adverse events. JCV antibodies constitute the main cause for discontinuation.