Exhaust Gas Recirculation (EGR) coolers are commonly used in diesel and modern gasoline engines to reduce the re-circulated gas temperature. A common problem with the EGR cooler is a reduction of the effectiveness due to the fouling layer primarily caused by thermophoresis, diffusion, and hydrocarbon condensation. Typically, effectiveness decreases rapidly at first, and asymptotically stabilizes over time. There are several hypotheses of this stabilizing phenomenon; one of the possible theories is a deposit removal mechanism. Verifying such a mechanism and finding out the correlation between the removal and stabilization tendency would be a key factor to understand and overcome the problem. Some authors have proposed that the removal is a possible influential factor, while other authors suggest that removal is not a significant factor under realistic conditions. This study identifies the effect of the deposit surface temperature on the removal mechanism with gas velocity and layer thickness variables and concludes that removal does occur under realistic conditions. To investigate the relation, the surface temperature is controlled by setting isothermal conditions of both blowing air and coolant, and the deposit build time is varied to find deposit thickness effects on removal. The blown-out particles are filtered out for mass weighing and size analysis. Additionally, a statistical analysis is conducted and an empirical removal equation is extracted to verify the removal mechanism through modeling. The results show that the removal mechanism has considerable correlation with deposit surface temperature as well as wall shear stress and deposit thickness.