Carcinoma cells initiate the metastatic cascade by inserting invasive pseudopodia through breaches in the basement membrane (BM), a specialized barrier of cross-linked, extracellular matrix macromolecules that underlies epithelial cells and ensheaths blood vessels. While BM invasion is the sine qua non of the malignant phenotype, the molecular programs that underlie this process remain undefined. To identify genes that direct BM remodeling and transmigration, we coupled high-resolution electron microscopy with an ex vivo model of invasion that phenocopies the major steps observed during the transition of carcinoma in situ to frank malignancy. Herein, a triad of membrane-anchored proteases, termed membrane type-1, type-2, and type-3 metalloproteinases, are identified as the triggering agents that independently confer cancer cells with the ability to proteolytically efface the BM scaffolding, initiate the assembly of invasive pseudopodia, and propagate transmigration. These studies characterize the first series of gene products capable of orchestrating the entire BM remodeling program that distinguishes the carcinomatous phenotype.