Hydrophobicity, the spontaneous segregation of oil and water, can be modified by surfactants. The way this modification occurs is studied at the oil-water interface for a range of alkanes and two ionic surfactants. A liquid interfacial monolayer, consisting of a mixture of alkane molecules and surfactant tails, is found. Upon cooling, it freezes at T(s), well above the alkane's bulk freezing temperature, T(b). The monolayer's phase diagram, derived by surface tensiometry, is accounted for by a mixtures-based theory. The monolayer's structure is measured by high-energy X-ray reflectivity above and below T(s). A solid-solid transition in the frozen monolayer, occurring approximately 3 °C below T(s), is discovered and tentatively suggested to be a rotator-to-crystal transition.