The first known magnetic mineral, magnetite (Fe$_3$O$_4$), has unusual properties which have fascinated mankind for centuries; it undergoes the Verwey transition at $T_{rm V}$ $sim$120 K with an abrupt change in structure and electrical conductivity. The mechanism of the Verwey transition however remains contentious. Here we use resonant inelastic X-ray scattering (RIXS) over a wide temperature range across the Verwey transition to identify and separate out the magnetic excitations derived from nominal Fe$^{2+}$ and Fe$^{3+}$ states. Comparison of the RIXS results with crystal-field multiplet calculations shows that the spin-orbital $dd$ excitons of the Fe$^{2+}$ sites arise from a tetragonal Jahn-Teller active polaronic distortion of the Fe$^{2+}$O$_6$ octahedra. These low-energy excitations, which get weakened for temperatures above 350 K but persist at least up to 550 K, are distinct from optical excitations and best explained as magnetic polarons.