By quantum Monte Carlo simulation of a realistic multiorbital Anderson impurity model, we study the spin-orbit interaction (SOI) of an Fe impurity in Au host metal. We show, for the first time, that the SOI is strongly renormalized by the quantum spin fluctuation. Based on this mechanism, we can explain why the gigantic spin Hall effect in Au with Fe impurities was observed in recent experiments, while it is not visible in the anomalous Hall effect. In addition, we show that the SOI is strongly renormalized by the Coulomb correlation U. Based on this picture, we can explain past discrepancies in the calculated orbital angular momenta for an Fe impurity in an Au host.