Soon after the discovery of the quantum spin Hall effect, it has been predicted that a magnetic impurity in the presence of strong Coulomb interactions will destroy the quantum spin Hall effect. However, the fate of the quantum spin Hall effect in the presence of magnetic impurities has not yet been experimentally investigated. Here, we report the successful experimental demonstration of a quantized spin Hall resistance in HgTe quantum wells dilutely alloyed with magnetic Mn atoms. These quantum wells exhibit an inverted band structure that is very similar to that of the undoped material. Micron sized devices of (Hg,Mn)Te quantum well (in the topological phase) show a quantized spin Hall resistance of h/2e2 at low temperatures and zero magnetic field. At finite temperatures, we observe signatures of the Kondo effect due to interaction between the helical edge channels and magnetic impurities. Our work lays the foundation for future investigations of magnetically doped quantum spin Hall materials towards the realization of chiral Majorana fermions.