Binding to negatively charged heparan sulfates (HS) at the cell surface is considered the first step in the internalization of cationic cell-penetrating peptides (CPPs). However, little is known about the relation of the characteristics of the HS-CPP interaction such as affinity, stoichiometry, and clustering with uptake. In this study, we investigated a collection of mutants of a cyclic CPP derived from human lactoferrin with respect to HS binding and uptake. The thermodynamic parameters of HS binding were determined by isothermal titration calorimetry, clustering of HS was investigated by dynamic light scattering, and cellular uptake by flow cytometry and confocal microscopy. Whereas mutations of non-arginine amino acids that are conserved across lactoferrins of different mammalia only had a minor effect on uptake efficiency, changes in the number of arginine residues influenced the uptake significantly. In general, introduction of arginine residues and cyclization improved the HS affinity and the ability to cluster HS. In particular, there was a strong negative correlation between stoichiometry and uptake, indicating that crosslinking of HS is the driving force for the uptake of arginine-rich CPPs. Using glycan microarrays presenting a collection of synthetic HS, we show that a minimal chain length of HS is required for peptide binding.