We investigate traveling solitons of a one-dimensional spin-orbit coupled Fermi superfluid in both topologically trivial and non-trivial 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 the presence of spin-orbit coupling, which strongly upshifts the energy level of the soliton-induced Andreev bound states towards the quasi-particle scattering continuum. 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 \(\pi\) 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.