Topological excitations are found throughout nature, in proteins and DNA, as dislocations in crystals, as vortices and solitons in superfluids and superconductors, and generally in the wake of symmetry-breaking phase transitions. In fermionic systems, topological defects may provide bound states for fermions that often play a crucial role for the system's transport properties. Famous examples are Andreev bound states inside vortex cores, fractionally charged solitons in relativistic quantum field theory, and the spinless charged solitons responsible for the high conductivity of polymers. However, the free motion of topological defects in electronic systems is hindered by pinning at impurities. Here we create long-lived solitons in a strongly interacting fermionic superfluid by imprinting a phase step into the superfluid wavefunction, and directly observe their oscillatory motion in the trapped superfluid. As the interactions are tuned from the regime of Bose-Einstein condensation (BEC) of tightly bound molecules towards the Bardeen-Cooper-Schrieffer (BCS) limit of long-range Cooper pairs, the effective mass of the solitons increases dramatically to more than 200 times their bare mass. This signals their filling with Andreev states and strong quantum fluctuations. For the unitary Fermi gas, the mass enhancement is more than fifty times larger than expectations from mean-field Bogoliubov-de Gennes theory. Our work paves the way towards the experimental study and control of Andreev bound states in ultracold atomic gases. In the presence of spin imbalance, the solitons created here represent one limit of the long sought-after Fulde-Ferrell-Larkin-Ovchinnikov (FFLO) state of mobile Cooper pairs.