Kondo correlation in a spin polarized quantum dot (QD) results from the dynamical formation of a spin singlet between the dot's net spin and a Kondo cloud of electrons in the leads, leading to enhanced coherent transport through the QD. We demonstrate here significant dephasing of such transport by coupling the QD and its leads to potential fluctuations in a nearby "potential detector." The qualitative dephasing is similar to that of a QD in the Coulomb blockade regime in spite of the fact that the mechanism of transport is quite different. A much stronger than expected suppression of coherent transport is measured, suggesting that dephasing is induced mostly in the "Kondo cloud" of electrons within the leads and not in the QD.