Binding of plasminogen (Pg) to cell-surface receptors colocalized with plasminogen activators promotes Pg activation and enables cells to utilize the proteolytic activity of plasmin (Pm). Proteolysis by Pm is necessary in several physiological and pathological processes requiring extracellular matrix degradation including cell migration, tumor cell invasion and metastasis. The binding of Pg to cell-surface receptors is regulated by two major structural features: L-lysine binding sites (LBS) and negatively charged sialic acid residues located on its carbohydrate chains. Pg uses its LBS to bind to a wide spectrum of cell-surface receptors whereas binding through its sialic acid residues is limited only to receptor proteins containing cationic pockets or lectin-like modules. In this review, we discuss both mechanisms, including the identification of DPP IV as a Pg receptor and the possible physiological role of Pg/Pm in complex with DPP IV and adenosine deaminase (ADA) and /or the Na+/H+ exchanger isoform NHE-3 in prostate cancer.