Solitons-solitary waves that maintain their shape as they propagate-occur as water waves in narrow canals, as light pulses in optical fibres and as quantum mechanical matter waves in superfluids and superconductors. Their highly nonlinear and localized nature makes them very sensitive probes of the medium in which they propagate. Here we create long-lived solitons in a strongly interacting superfluid of fermionic atoms and directly observe their motion. As the interactions are tuned from the regime of Bose-Einstein condensation of tightly bound molecules towards the Bardeen-Cooper-Schrieffer limit of long-range Cooper pairs, the solitons' effective mass increases markedly, to more than 200 times their bare mass, signalling strong quantum fluctuations. This mass enhancement is more than 50 times larger than the theoretically predicted value. Our work provides a benchmark for theories of non-equilibrium dynamics of strongly interacting fermions.