Focal adhesions are large multi-protein assemblies that form at the basal surface of cells on planar dishes, and that mediate cell signalling, force transduction and adhesion to the substratum. Although much is known about focal adhesion components in two-dimensional (2D) systems, their role in migrating cells in a more physiological three-dimensional (3D) matrix is largely unknown. Live-cell microscopy shows that for cells fully embedded in a 3D matrix, focal adhesion proteins, including vinculin, paxillin, talin, α-actinin, zyxin, VASP, FAK and p130Cas, do not form aggregates but are diffusely distributed throughout the cytoplasm. Despite the absence of detectable focal adhesions, focal adhesion proteins still modulate cell motility, but in a manner distinct from cells on planar substrates. Rather, focal adhesion proteins in matrix-embedded cells regulate cell speed and persistence by affecting protrusion activity and matrix deformation, two processes that have no direct role in controlling 2D cell speed. This study shows that membrane protrusions constitute a critical motility/matrix-traction module that drives cell motility in a 3D matrix.