Peptidylarginine deiminase 4 (PAD4) is citrullinating enzyme involvement in pathogenesis of rheumatoid arthritis. Activation of this enzyme by calcium remains unclear as calcium levels in the human body are typically too low for full activity. It has been proposed that allosteric activators of PAD4 improve calcium affinity of the enzyme. Several PAD4 activators have been identified recently, including optimized synthetic cyclic peptides or specific antibodies. They are results of iterative optimization or in vitro selection, not physiological molecules. Herein, we investigated the activation of PAD4 by glycosaminoglycans (GAGs) using heparin as model. We employed activity assays, chromatography, molecular interaction measurements (MST and SPR) and CryoEM to show activation of PAD4 and formation of PAD4-heparin complex. Our data show that PAD4 binds heparin, even at high salt concentrations. PAD4 is activated in the presence of heparin at sub-optimal concentrations of calcium and we observe that the activation mechanism depends on increasing PAD4 calcium affinity. We further demonstrate that activation by heparin depends on the length and charge of GAG molecule. Direct binding measurements using MST and SPR confirmed a tight interaction between PAD4 and heparin. CryoEM structures revealed PAD4 bound to heparin oligomers of varying lengths, showing different binding modes and supramolecular organizations of PAD4-heparin complexes. Mutagenesis studies indicated that PAD4 dimerization is essential for efficient activation. We demonstrate that cell surface binding of PAD4 depends on the GAG composition using CHO cell models and that heparin induces histone H3.1 citrullination and DNA release from human neutrophils. Additionally, other GAGs were identified as PAD4 activators. In summary, our findings present the first natural activators of PAD4, potentially explaining its role in physiological processes related to rheumatoid arthritis development.