Glycosaminoglycans (GAGs) affect the efficiency of cellular uptake of a wide range of cell penetrating peptides (CPPs). GAGs have been proposed to cluster with CPPs at the cell surface before uptake but little is known about the formation or stability of CPP-GAG clusters. Here we apply a combination of heparin affinity chromatography, dynamic light scattering, and fluorescence spectroscopy to characterize the formation, stability, and size of the clusters formed between CPPs and heparin. Under conditions similar to those used in cell uptake experiments the CPP, penetratin (Antp), was observed to form significantly more stable clusters with heparin than the CPP TAT, despite TAT showing a comparable affinity for heparin. This difference in cluster stability may explain the origins of the preferred cell uptake pathways followed by Antp and TAT, and may be an important parameter for optimizing the efficiency of designed CPP delivery vectors.