Motivated by the premise that superconductivity in iron-based superconductors is unconventional and mediated by spin fluctuations, an intense research effort has been focused on characterizing the spin-excitation spectrum in the magnetically ordered parent phases of the Fe pnictides and chalcogenides. For these undoped materials, it is well established that the spin-excitation spectrum consists of sharp, highly dispersive magnons. The fate of these high-energy magnetic modes upon sizable doping with holes is hitherto unresolved. Here we demonstrate, using resonant inelastic X-ray scattering, that optimally hole-doped superconducting Ba 0.6 K 0.4 Fe 2 As 2 retains well-defined, dispersive high-energy modes of magnetic origin. These paramagnon modes are softer than, though as intense as, the magnons of undoped antiferromagnetic BaFe 2 As 2. The persistence of spin excitations well into the superconducting phase suggests that the spin fluctuations in Fe-pnictide superconductors originate from a distinctly correlated spin state. This connects Fe pnictides to cuprates, for which, in spite of fundamental electronic structure differences, similar paramagnons are present.