The invasion of migratory cells through connective tissues involves metallo- and serine types of cell surface proteases. We show that formation of a novel protease complex, consisting of the membrane-bound prolyl peptidases seprase and dipeptidyl peptidase IV (DPPIV), at invadopodia of migratory fibroblasts is a prerequisite for cell invasion and migration on a collagenous matrix. Seprase and DPPIV form a complex on the cell surface that elicits both gelatin binding and gelatinase activities localized at invadopodia of cells migrating on collagenous fibers. The protease complex participates in the binding to gelatin and localized gelatin degradation, cellular migration, and monolayer wound closure. Serine protease inhibitors can block the gelatinase activity and the localized gelatin degradation by cells. Antibodies to the gelatin-binding domain of DPPIV reduce the cellular abilities of the proteases to degrade gelatin but do not affect cellular adhesion or spreading on type I collagen. Furthermore, expression of the seprase-DPPIV complex is restricted to migratory cells involved in wound closure in vitro and in connective tissue cells during closure of gingival wounds but not in differentiated tissue cells. Thus, we have identified cell surface proteolytic activities, which are non-metalloproteases, seprase and DPPIV, that are responsible for the tissue-invasive phenotype.