A new experimental arrangement is described for acquiring sum-frequency (SF) spectra from surfactants at the oil-water interface. The key features of this approach are the stabilization of a thin oil film between a sapphire prism and an aqueous phase and the use of total internal reflection to enhance the total signal and discriminate against signals from other interfaces in the system. With this new methodology, the first SF vibrational spectra of surfactant monolayers at an alkane-water interface were obtained. Surface tensiometry was used to characterize the monolayers further. The structure of monolayers of the cationic surfactant hexadecyltrimethylammonium bromide (CTAB) at the hexadecane-water interface was determined by sum-frequency spectroscopy (SFS) and compared with monolayers of CTAB at the air-water interface. At low concentrations, CTAB/hexadecane showed the expected features in the C-H stretching region, characteristic of a conformationally disordered monolayer. As the bulk concentration approached the critical micelle concentration, the spectra changed to one characteristic of a more ordered, upright conformation. Ellipsometric measurements supported this conclusion. This qualitative structural change is not observed in analogous monolayers at the air-water interface or CCl4-water interface or in surfactant solutions in contact with a hydrophobic solid surface.