One of the severe acute respiratory syndrome coronavirus 2 (SARS-CoV-2) virulence factors is the ability to interact with high affinity to the ACE2 receptor, which mediates viral entry into cells. The results of our study demonstrate that within a few passages in cell culture, both the natural isolate of SARS-CoV-2 and the recombinant cDNA-derived variant acquire an additional ability to bind to heparan sulfate (HS). This promotes a primary attachment of viral particles to cells before their further interactions with the ACE2. Interaction with HS is acquired through multiple mechanisms. These include (i) accumulation of point mutations in the N-terminal domain (NTD) of the S protein, which increases the positive charge of the surface of this domain, (ii) insertions into the NTD of heterologous peptides containing positively charged amino acids, and (iii) mutation of the first amino acid downstream of the furin cleavage site. This last mutation affects S protein processing, transforms the unprocessed furin cleavage site into the heparin-binding peptide, and makes viruses less capable of syncytium formation. These viral adaptations result in higher affinity of viral particles to heparin, dramatic increase in plaque sizes, more efficient viral spread, higher infectious titers, and 2 orders of magnitude higher infectivity. The detected adaptations also suggest an active role of NTD in virus attachment and entry. As in the case of other RNA-positive (RNA⁺) viruses, evolution to HS binding may result in virus attenuation in vivo. IMPORTANCE The spike protein of SARS-CoV-2 is a major determinant of viral pathogenesis. It mediates binding to the ACE2 receptor and, later, fusion of viral envelope and cellular membranes. The results of our study demonstrate that SARS-CoV-2 rapidly evolves during propagation in cultured cells. Its spike protein acquires mutations in the NTD and in the P1' position of the furin cleavage site (FCS). The amino acid substitutions or insertions of short peptides in NTD are closely located on the protein surface and increase its positive charge. They strongly increase affinity of the virus to heparan sulfate, make it dramatically more infectious for the cultured cells, and decrease the genome equivalent to PFU (GE/PFU) ratio by orders of magnitude. The S686G mutation also transforms the FCS into the heparin-binding peptide. Thus, the evolved SARS-CoV-2 variants efficiently use glycosaminoglycans on the cell surface for primary attachment before the high-affinity interaction of the spikes with the ACE2 receptor.