The extracellular matrix (ECM) proteins fibronectin (FN) and type I collagen (collagen I) are codistributed in many tissues, and collagens have been shown to depend on an FN matrix for fibrillogenesis. Microscopic analysis of a fibroblast ECM showed colocalization of procollagen I with FN fibrils, and proteolytic cleavage of procollagen to initiate fibril formation was significantly reduced with inhibition of FN matrix assembly. We examined the role of FN matrix in procollagen processing by the C-propeptide proteinase bone morphogenetic protein 1 (BMP-1). We found that BMP-1 binds to a cell-assembled ECM in a dose-dependent manner and that, like procollagen, BMP-1 colocalizes with FN fibrils in the matrix microenvironment. Binding studies with FN fragments identified a binding site in FN's primary heparin-binding domain. In solution, BMP-1-FN interactions and BMP-1 cleavage of procollagen I were both enhanced by the presence of heparin, suggesting a role for heparin in complex formation during proteolysis. Indeed, addition of heparin enhanced the rate of procollagen cleavage by matrix-bound BMP-1. Our results show that matrix localization of this proteinase facilitates the initiation of collagen assembly and suggest a model in which FN matrix and associated heparan sulfate act as a scaffold to organize enzyme and substrate for procollagen processing.