Background: Natalizumab treatment is associated with progressive multifocal leukoencephalopathy (PML) development. Treatment duration, prior immunosuppressant use, and JCV serostatus are currently used for risk stratification, but PML incidence stays high. Anti-JCV antibody index and L-selectin (CD62L) have been proposed as additional risk stratification parameters. Objective: This study aimed at verifying and integrating both parameters into one algorithm for risk stratification. Methods: Multicentric, international cohorts of natalizumab-treated MS patients were assessed for JCV index (1921 control patients and nine pre-PML patients) and CD62L (1410 control patients and 17 pre-PML patients). Results: CD62L values correlate with JCV serostatus, as well as JCV index values. Low CD62L in natalizumab-treated patients was confirmed and validated as a biomarker for PML risk with the risk factor “CD62L low” increasing a patient’s relative risk 55-fold ( p < 0.0001). Validation efforts established 86% sensitivity/91% specificity for CD62L and 100% sensitivity/59% specificity for JCV index as predictors of PML. Using both parameters identified 1.9% of natalizumab-treated patients in the reference center as the risk group. Conclusions: Both JCV index and CD62L have merit for risk stratification and share a potential biological relationship with implications for general PML etiology. A risk algorithm incorporating both biomarkers could strongly reduce PML incidence.