Cell invasion through basement membranes is crucial during morphogenesis and cancer metastasis. Here, we genetically dissect this process during anchor-cell invasion into the vulval epithelium in C. elegans. We have identified the fos transcription factor ortholog fos-1 as a critical regulator of basement-membrane removal. In fos-1 mutants, the gonadal anchor cell extends cellular processes normally toward vulval cells, but these processes fail to remove the basement membranes separating the gonad from the vulval epithelium. fos-1 is expressed in the anchor cell and controls invasion cell autonomously. We have identified ZMP-1, a membrane-type matrix metalloproteinase, CDH-3, a Fat-like protocadherin, and hemicentin, a fibulin family extracellular matrix protein, as transcriptional targets of FOS-1 that promote invasion. These results reveal a key genetic network that controls basement-membrane removal during cell invasion.