Multiple myeloma arises when malignant plasma cells invade and form multiple tumors in the bone marrow. High levels of heparanase (HPSE) correlate with poor prognosis in myeloma patients. A likely target of the enzyme is the heparan sulfate (HS) proteoglycan syndecan-1 (Sdc1, CD138), which is highly expressed on myeloma cells and contributes to poor prognosis in this disease. We find that HPSE promotes an invasive phenotype mediated by the very late antigen-4 (VLA-4, or α4β1 integrin) in myeloma cells plated on either fibronectin (FN) or vascular endothelial cell adhesion molecule-1 (VCAM-1), ligands that are prevalent in the bone marrow. The phenotype depends on vascular endothelial cell growth factor receptor-2 (VEGFR2), which is aberrantly expressed in myeloma, and is characterized by a highly protrusive lamellipodium and cell invasion. HPSE-mediated trimming of the HS on Sdc1 and subsequent matrix metalloproteinase-9-mediated shedding of the syndecan exposes a juxtamembrane site in Sdc1 that binds VEGFR2 and VLA-4, thereby coupling VEGFR2 to the integrin. Shed Sdc1 can be mimicked by recombinant Sdc1 ectodomain or by a peptide based on its binding motif, which causes VLA-4 to re-orient from the lagging edge (uropod) to the leading edge of migrating cells, couple with and activate VEGFR2. Peptides (called 'synstatins') containing only the VLA-4 or VEGFR2 binding sites competitively inhibit invasion, as they block coupling of the receptors. This mechanism is also utilized by vascular endothelial cells, in which it is also activated by HPSE, during endothelial cell tube formation. Collectively, our findings reveal for the first time the mechanism through which HPSE modulates Sdc1 function to promote both tumor cell invasion and angiogenesis, thereby driving multiple myeloma progression. The inhibitory synstatins, or inhibitors of HPSE enzyme activity, are likely to show promise as therapeutics against myeloma extravasation and spread.