Phenol-soluble modulins (PSMs), such as α-PSMs, β-PSMs, and δ-toxin, are virulence peptides secreted by different Staphylococcus aureus strains. PSMs are able to form amyloid fibrils, which may strengthen the biofilm matrix that promotes bacterial colonization of and extended growth on surfaces (e.g., cell tissue) and increases antibiotic resistance. Many components contribute to biofilm formation, including the human-produced highly sulfated glycosaminoglycan heparin. Although heparin promotes S. aureus infection, the molecular basis for this is unclear. Given that heparin is known to induce fibrillation of a wide range of proteins, we hypothesized that heparin aids bacterial colonization by promoting PSM fibrillation. Here, we address this hypothesis using a combination of thioflavin T-fluorescence kinetic studies, CD, FTIR, electron microscopy, and peptide microarrays to investigate the mechanism of aggregation, the structure of the fibrils, and identify possible binding regions. We found that heparin accelerates fibrillation of all α-PSMs (except PSMα2) and δ-toxin but inhibits β-PSM fibrillation by blocking nucleation or reducing fibrillation levels. Given that S. aureus secretes higher levels of α-PSM than β-PSM peptides, heparin is therefore likely to promote fibrillation overall. Heparin binding is driven by multiple positively charged lysine residues in α-PSMs and δtoxins, the removal of which strongly reduced binding affinity. Binding of heparin did not affect the structure of the resulting fibrils, that is, the outcome of the aggregation process. Rather, heparin provided a scaffold to catalyze or inhibit fibrillation. Based on our findings, we speculate that heparin may strengthen the bacterial biofilm and therefore enhance colonization via increased PSM fibrillation.