In vivo, cells migrate on complex three-dimensional (3D) fibrous matrices, which has made investigation of the key molecular and physical mechanisms that drive cell migration difficult. Using reductionist approaches based on 3D electrospun fibers, we report for various cell types that single-cell migration along fibronectin-coated nanofibers is associated with lateral actin-based waves. These cyclical waves have a fin-like shape and propagate up to several hundred micrometers from the cell body, extending the leading edge and promoting highly persistent directional movement. Cells generate these waves through balanced activation of the Rac1/N-WASP/Arp2/3 and Rho/formins pathways. The waves originate from one major adhesion site at leading end of the cell body, which is linked through actomyosin contractility to another site at the back of the cell, allowing force generation, matrix deformation and cell translocation. By combining experimental and modeling data, we demonstrate that cell migration in a fibrous environment requires the formation and propagation of dynamic, actin based fin-like protrusions.