Glycosaminoglycans (GAGs) are complex highly charged linear polysaccharides that have a variety of roles in biological processes. We report the first use of molecular dynamics (MD) free energy calculations using the MM/PBSA method to investigate the binding of GAGs to protein molecules, namely the platelet endothelial cell adhesion molecule 1 (PECAM-1) and annexin A2. Calculations of the free energy of the binding of heparin fragments of different sizes reveal the existence of a region of low GAG-binding affinity in domains 5-6 of PECAM-1 and a region of high affinity in domains 2-3, consistent with experimental data and ligand-protein docking studies. A conformational hinge movement between domains 2 and 3 was observed, which allows the binding of heparin fragments of increasing size (pentasaccharides to octasaccharides) with an increasingly higher binding affinity. Similar simulations of the binding of a heparin fragment to annexin A2 reveal the optimization of electrostatic and hydrogen bonding interactions with the protein and protein-bound calcium ions. In general, these free energy calculations reveal that the binding of heparin to protein surfaces is dominated by strong electrostatic interactions for longer fragments, with equally important contributions from van der Waals interactions and vibrational entropy changes, against a large unfavorable desolvation penalty due to the high charge density of these molecules.