Directional cell migration in dense three-dimensional (3D) environments critically depends upon shape adaptation and is impeded depending on the size and rigidity of the nucleus. Accordingly, the nucleus is primarily understood as a physical obstacle, however, its pro-migratory functions by step-wise deformation and reshaping remain unclear. Using atomic force spectroscopy, time-lapse fluorescence microscopy and shape change analysis tools, we determined nuclear size, deformability, morphology and shape change of HT1080 fibrosarcoma cells expressing the Fucci cell cycle indicator or being pre-treated with chromatin-decondensating agent TSA. We show oscillating peak accelerations during migration through 3D collagen matrices and microdevices that occur during shape reversion of deformed nuclei (recoil), and increase with confinement. During G1 cell cycle phase, nucleus stiffness was increased and yielded further increased speed fluctuations together with sustained cell migration rates in confinement as compared to interphase populations, or to periods of intrinsic nuclear softening in the S/G2 cell cycle phase. Likewise, nuclear softening by pharmacological chromatin decondensation or after lamin A/C depletion reduced peak oscillations in confinement. In conclusion, deformation and recoil of the stiff nucleus contributes to saltatory locomotion in dense tissues.