Background: Smoking has been associated with increased multiple sclerosis (MS) risk, disease worsening, and progression in MS patients. Furthermore, interactions between smoking and human leukocyte antigen (HLA) genes have been shown for MS risk. Recently, we found that smoking was associated with an increased relapse rate in interferon-beta-treated relapsing-remitting multiple sclerosis (RRMS) patients. Objectives: We examined the association between smoking and relapses in natalizumab-treated RRMS patients. Second, we investigated if an interaction between smoking and HLA-DRB1*15:01 or HLA-A*02:01 affected the number of relapses during treatment. Methods: In this observational cohort study, 355 natalizumab-treated RRMS patients were assessed. Prespecified criteria excluded 62 patients. Clinical data from the starting of treatment to the two-year follow-up visit were collected. Smoking status was obtained by a questionnaire survey. TaqMan allelic discrimination was used for genotyping of tag single-nucleotide polymorphisms (SNPs) for HLA-DRB1*15:01 and HLA-A*02:01. Negative binomial regression analysis was used to analyze the association between relapse rate and smoking intensity and HLA. Results: One pack of cigarettes (20 cigarettes) per day during natalizumab treatment increased the relapse rate during treatment with 38% (incidence rate ratio (IRR) = 1.38, 95% confidence interval (CI): 1.08–1.77, p = 0.01). No association or interaction was found between smoking and HLA-DRB1*15:01 or HLA-A*02:01, respectively. Conclusion: Smoking intensity was significantly associated with the number of relapses during natalizumab treatment.