A classical spin which is antiferromagnetically coupled to a system of strongly correlated conduction electrons is shown to exhibit unconventional real-time dynamics which cannot be described by Gilbert damping. Depending on the strength of the local Coulomb interaction U, the two main electronic dissipation channels, namely transport of excitations via correlated hopping and via excitations of correlation-induced magnetic moments, become active on largely different time scales. We demonstrate that correlations can lead to a strongly suppressed relaxation which so far has been observed in purely electronic systems only and which is governed here by proximity to the divergent magnetic time scale in the infinite-U limit.