Accurate identification of substrates of a protease is critical in defining its physiological functions. We previously predicted that Dsg-2 (desmoglein-2), a desmosomal protein, is a candidate substrate of the transmembrane serine protease matriptase. The present study is an experimental validation of this prediction. As demanded by our published method PNSAS [Prediction of Natural Substrates from Artificial Substrate of Proteases; Venkatraman, Balakrishnan, Rao, Hooda and Pol (2009) PLoS ONE 4, e5700], this enzyme-substrate pair shares a common subcellular distribution and the predicted cleavage site is accessible to the protease. Matriptase knock-down cells showed enhanced immunoreactive Dsg-2 at the cell surface and formed larger cell clusters. When matriptase was mobilized from intracellular storage deposits to the cell surface there was a decrease in the band intensity of Dsg-2 in the plasma membrane fractions with a concomitant accumulation of a cleaved product in the conditioned medium. The exogenous addition of pure active recombinant matriptase decreased the surface levels of immunoreactive Dsg-2, whereas the levels of CD44 and E-cadherin were unaltered. Dsg-2 with a mutation at the predicted cleavage site is resistant to cleavage by matriptase. Thus Dsg-2 seems to be a functionally relevant physiological substrate of matriptase. Since breakdown of cell-cell contact is the first major event in invasion, this reciprocal relationship is likely to have a profound role in cancers of epithelial origin. Our algorithm has the potential to become an integral tool for discovering new protease-substrate pairs.