PML is a progressive and mostly fatal demyelinating disease caused by JC virus infection and destruction of infected oligodendrocytes in multiple brain foci of susceptible individuals. While JC virus is highly prevalent in the human population, PML is a rare disease that exclusively afflicts only a small percentage of immunocompromised individuals including those affected by HIV (AIDS) or immunosuppressive drugs. Viral- and/or host-specific factors, and not simply immune status, must be at play to account for the very large discrepancy between viral prevalence and low disease incidence. Here, we show that several amino acids on the surface of the JC virus capsid protein VP1 display accelerated evolution in viral sequences isolated from PML patients but not in sequences isolated from healthy subjects. We provide strong evidence that at least some of these mutations are involved in binding of sialic acid, a known receptor for the JC virus. Using statistical methods of molecular evolution, we performed a comprehensive analysis of JC virus VP1 sequences isolated from 55 PML patients and 253 sequences isolated from the urine of healthy individuals and found that a subset of amino acids found exclusively among PML VP1 sequences is acquired via adaptive evolution. By modeling of the 3-D structure of the JC virus capsid, we showed that these residues are located within the sialic acid binding site, a JC virus receptor for cell infection. Finally, we go on to demonstrate the involvement of some of these sites in receptor binding by demonstrating a profound reduction in hemagglutination properties of viral-like particles made of the VP1 protein carrying these mutations. Collectively, these results suggest that a more virulent PML causing phenotype of JC virus is acquired via adaptive evolution that changes viral specificity for its cellular receptor(s).