Sum frequency generation (SFG) vibrational spectroscopy has been applied to study protein adsorption on native oxide-covered polycrystalline Ti surfaces. We demonstrated that both H2O2 solution cleaning and plasma treating can effectively eliminate the unavoidable natural hydrocarbon contamination formed during storage of Ti samples in air. As the presence and potential biological role of this contamination has been a concern of recent studies of inorganic biomaterial interfaces, comparison of the protein adsorption behaviors on the contaminated and cleaned Ti samples has been performed using SFG. Various experiments indicate that hydrocarbon contamination does not greatly affect adsorption of soft proteins on native oxide-covered Ti surfaces. Additional SFG studies show that methyl groups of adsorbed bovine serum albumin have a relatively ordered structure on oxidized Ti, which is slightly affected by the cleaning method. Our data also reveal time-dependent changes of the protein structures during the adsorption process.