During angiogenesis, endothelial cells (ECs) degrade their surrounding extracellular matrix (ECM) to facilitate invasion. How interactions between ECs and other cells within their microenvironment facilitate this process is only partially understood. We have utilized a tractable 3D co-culture model to investigate the proteolytic mechanisms by which pre-committed or more highly committed mesenchymal cells stimulate capillary formation. On their own, ECs invade their surrounding matrix, but do not form capillaries. However, in the presence of either mesenchymal stem cells (MSCs) or fibroblasts, ECs form polarized, tubular structures that are intimately associated with mesenchymal cells. Further, ECs up-regulate gene expression of several extracellular proteases upon co-culture with either mesenchymal cell type. The administration of both broad spectrum and specific protease inhibitors demonstrated that MSC-stimulated capillary formation relied solely on membrane-type matrix metalloproteinases (MT-MMPs) while fibroblast-mediated sprouting proceeded independent of MMP inhibition unless the plasminogen activator/plasmin axis was inhibited in concert. While other studies have established a role for the ECM itself in dictating proteolysis and matrix degradation during capillary morphogenesis, the present study illustrates that heterotypic cellular interactions within the microenvironment can direct the proteolytic mechanisms required for capillary formation.