Magnetic impurities play an important role in many spintronics-related materials. Motivated by this fact, we study the anomalous Hall effect in the presence of magnetic impurities, focusing on two-dimensional electron systems with Rashba spin-orbit coupling. We find a highly nonlinear dependence on the impurity polarization, including possible sign changes. At small impurity magnetizations, this is a consequence of the remarkable result that the linear term is independent of the spin-orbit coupling strength. Near saturation of the impurity spins, the anomalous Hall conductivity can be resonantly enhanced, due to interference between potential and magnetic scattering.