Invasive cancer cells are believed to breach the basement membrane (BM) using specialized protrusions called invadopodia. We found that the crossing of a native BM is a three-stage process: invadopodia indeed form and perforate the BM, elongate into mature invadopodia, and then guide the cell toward the stromal compartment. We studied the remodeling of cytoskeleton networks during invadopodia formation and elongation using ultrastructural analysis, spatial distribution of molecular markers, and RNA interference silencing of protein expression. We show that formation of invadopodia requires only the actin cytoskeleton and filopodia- and lamellipodia-associated proteins. In contrast, elongation of invadopodia is mostly dependent on filopodial actin machinery. Moreover, intact microtubules and vimentin intermediate filament networks are required for further growth. We propose that invadopodia form by assembly of dendritic/diagonal and bundled actin networks and then mature by elongation of actin bundles, followed by the entry of microtubules and vimentin filaments. These findings provide a link between the epithelial to mesenchymal transition and BM transmigration.