Several pathogenic bacteria, including Listeria monocytogenes, use an F-actin motility process to spread between mammalian cells. Actin 'comet tails' propel Listeria through the cytoplasm, resulting in bacteria-containing membrane protrusions that are internalized by neighbouring cells. The mechanism by which Listeria overcomes cortical tension to generate protrusions is unknown. Here, we identify bacterial and host proteins that directly regulate protrusions. We show that efficient spreading between polarized epithelial cells requires the secreted Listeria virulence protein InlC (internalin C). We next identify the mammalian adaptor protein Tuba as a ligand of InlC. InlC binds to a carboxy-terminal SH3 domain in Tuba, which normally engages the human actin regulatory protein N-WASP. InlC promotes protrusion formation by inhibiting Tuba and N-WASP activity, probably by impairing binding of N-WASP to the Tuba SH3 domain. Tuba and N-WASP are known to control the structure of apical junctions in epithelial cells. We demonstrate that, by inhibiting Tuba and N-WASP, InlC makes taut apical junctions become slack. Experiments with myosin II inhibitors indicate that InlC-mediated perturbation of apical junctions accounts for the role of this bacterial protein in protrusion formation. Collectively, our results suggest that InlC promotes bacterial dissemination by relieving cortical tension, thereby enhancing the ability of motile bacteria to deform the plasma membrane into protrusions.