We investigate traveling solitons of a one- or two-dimensional spin-orbit-coupled Fermi superfluid in both topologically trivial and nontrivial regimes by solving the static and time-dependent Bogoliubov-de Gennes equations. We find a critical velocity v_{h} for traveling solitons that is much smaller than the value predicted using the Landau criterion due to spin-orbit coupling. Above v_{h}, our time-dependent simulations in harmonic traps indicate that traveling solitons decay by radiating sound waves. In the topological phase, we predict the existence of peculiar Majorana solitons, which host two Majorana fermions and feature a phase jump of π across the soliton, irrespective of the velocity of travel. These unusual properties of Majorana solitons may open an alternative way to manipulate Majorana fermions for fault-tolerant topological quantum computations.