Glycosaminoglycans (GAGs) are long chains of negatively charged sulfated polysaccharides. They are often found to be covalently attached to proteins and form proteoglycans in the extracellular matrix (ECM). Many proteins bind GAGs through electrostatic interactions. GAG-binding proteins (GBPs) are involved in diverse physiological activities ranging from bacterial infections to cell-cell/cell-ECM contacts. This thesis is devoted to understanding how interactions between GBPs and their receptors modulate biological phenomena. Bacteria express GBPs on surface that facilitate dissemination and colonization by attaching to host ECM. The first GBP investigated in this thesis is decorin binding protein (DBP) found on the surface of Borrelia burgdorferi, causative pathogens in Lyme disease. DBPs bind GAGs of decorin, a proteoglycan in ECM. Of the two isoforms, DBPB is less studied than DBPA. In current work, structure of DBPB from B. burgdorferi and its GAG interactions were investigated using solution NMR techniques. DBPB adopts a five-helical structure, similar to DBPA. Despite similar GAG affinities, DBPB has its primary GAG-binding site on the lysine-rich C terminus, which is different from DBPA. Besides GAGs, GBPs in ECM also interact with cell surface receptors, such as integrins. Integrins belong to a big family of heterodimeric transmembrane proteins that receive extracellular cues and transmit signals bidirectionally to regulate cell adhesion, migration, growth and survival. The second part of this thesis focuses on αM I-domain of the promiscuous integrin αMβ2 (Mac-1 or CD11b/CD18) and explores the structural mechanism of αM I-domain interactions with pleiotrophin (PTN) and platelet factor 4 (PF4), which are cationic proteins with high GAG affinities. After completing the backbone assignment of αM I-domain, paramagnetic relaxation enhancement (PRE) experiments were performed to show that both PTN and PF4 bind αM I-domain using metal ion dependent adhesion site (MIDAS) in an Mg2+ independent way, which differs from the classical Mg2+ dependent mechanism used by all known integrin ligands thus far. In addition, NMR relaxation dispersion analysis revealed unique inherent conformational dynamics in αM I-domain centered around MIDAS and the crucial C-terminal helix. These dynamic motions are potentially functionally relevant and may explain the ligand promiscuity of the receptor, but requires further studies.