Metastasis involves the invasion of cancer cells across both the extracellular matrix and cellular barriers, and an evolving theme is that epithelial-to-mesenchymal transition (EMT) may mediate invasive cellular behavior. Previously, we isolated and analyzed a subpopulation of PC-3 prostate cancer cells, TEM4-18, and found that these cells both invaded an endothelial barrier more efficiently and exhibited enhanced metastatic colonization in vivo. Transendothelial migration of these cells depended on expression of ZEB1, a known regulator of EMT. Surprisingly, these cells were much less invasive than parental PC-3 cells in assays that involve matrix barriers. Here, we report that TEM4-18 cells express significantly reduced levels of two subunits of laminin-332 (β3 and γ2) and that exogenous laminin-332, or co-culture with laminin-332-expressing cells, rescues the in vitro invasion phenotype in these cells. Stable knockdown of ZEB1 in prostate cancer cells up-regulated LAMC2 and ITGB4 mRNA and protein and resulted in a concomitant increase in Transwell migration. Using chromatin immunoprecipitation (ChIP), we show that ZEB1 directly interacts with the promoters of LAMC2 and ITGB4. These results provide a novel molecular basis for reduced laminin-332 observed in clinical prostate cancer specimens and demonstrate a context-dependent role for EMT in invasive cellular behavior.