There are an increasing number of treatments available for multiple sclerosis (MS). The early identification of optimal responders to individual treatments is important to achieve individualized therapy. With this aim, we performed a multicenter retrospective longitudinal study including 186 MS patients treated with natalizumab who were followed for 2 years. We analyzed the following variables at recruitment: sex, current age, age at disease onset, disease duration, EDSS, number of T2 and Gd + lesions, IgG and IgM oligoclonal bands, HLA class II (DR, DRB, DQA, DQB, and DRB1*15:01), IgG and IgM antibody titers against human herpesvirus 6 (HHV-6) and the antibody response to Epstein-Barr virus (EBV) through the measurement of the anti-EBNA-1 and anti-VCA IgG titers, in relation to clinical response (no relapses or disability progression), and to NEDA-3 (no evidence of disease activity in terms of clinical response and no changes in MRI scans either) after 2-years follow-up. Baseline EDSS score, baseline EBNA-1 IgG titers and percentage change of HHV6 IgG titers between baseline and 6 month visits were significantly different in clinical responders and in NEDA-3 status (all of them remained significant in the multivariate analysis). We identified three variables for the early identification of natalizumab optimal responders in a rapid and cost-effective approach.