Large scale computer simulations are used to elucidate a longstanding controversy regarding the existence, or otherwise, of spin waves in paramagnetic BCC iron. Spin dynamics simulations of the dynamic structure factor of a Heisenberg model of Fe with first principles interactions reveal that well defined peaks persist far above Curie temperature T_c. At large wave vectors these peaks can be ascribed to propagating spin waves, at small wave vectors the peaks correspond to over-damped spin waves. Paradoxically, spin wave excitations exist despite only limited magnetic short-range order at and above T_c.