Cell migration on two-dimensional substrates is typically characterized by lamellipodia at the leading edge, mature focal adhesions and spread morphologies. These observations result from adherent cell migration studies on stiff, elastic substrates, because most cells do not migrate on soft, elastic substrates. However, many biological tissues are soft and viscoelastic, exhibiting stress relaxation over time in response to a deformation. Here, we have systematically investigated the impact of substrate stress relaxation on cell migration on soft substrates. We observed that cells migrate minimally on substrates with an elastic modulus of 2 kPa that are elastic or exhibit slow stress relaxation, but migrate robustly on 2-kPa substrates that exhibit fast stress relaxation. Strikingly, migrating cells were not spread out and did not extend lamellipodial protrusions, but were instead rounded, with filopodia protrusions extending at the leading edge, and exhibited small nascent adhesions. Computational models of cell migration based on a motor-clutch framework predict the observed impact of substrate stress relaxation on cell migration and filopodia dynamics. Our findings establish substrate stress relaxation as a key requirement for robust cell migration on soft substrates and uncover a mode of two-dimensional cell migration marked by round morphologies, filopodia protrusions and weak adhesions.