A cleaning process resulting in atomically smooth, hydrogen-terminated, silicon surface that would inhibit formation of native silicon oxide is needed for high-k gate dielectric deposition. Various cleaning methods thus need to be tested in terms of resistance to native oxide formation. Native oxide re-growth is studied as a function of exposure time to atmospheric ambient using ellipsometry. Hafnium dioxide film (k ~23) is deposited on the as-cleaned substrates by electron beam evaporation and subsequently annealed in hydrogen. The difference in the effective oxide thickness re-grown on surfaces treated with the conventional RCA and modified Shiraki cleaning methods, after one-hour exposure, can be as large as 2 Å. This is significant in device applications demanding equivalent oxide thickness less than 20 Å. The degree of hydrogen passivation, surface micro-roughness and organic removal capability are considered to be the main factors that explain the differences between the cleaning methods. Data derived from capacitance-voltage analysis of test capacitors verified the trend observed in the native oxide thickness measurements. An increase of 10~15 % in accumulation capacitance is observed in the samples treated by the new cleaning method.