Alkanes longer than n = 6 carbons do not spread on the water surface, but condense in a macroscopic lens. However, adding trimethylammonium-based surfactants, C(m)TAB, in submillimolar concentrations causes the alkanes to spread and form a single Langmuir-Gibbs (LG) monolayer of mixed alkanes and surfactant tails, which coexists with the alkane lenses. Upon cooling, this LG film surface-freezes at a temperature T(s) above the bulk freezing temperature T(b). The thermodynamics of surface freezing (SF) of these LG films is studied by surface tension measurements for a range of alkanes (n = 12-21) and surfactant alkyl lengths (m = 14, 16, 18), at several concentrations c. The surface freezing range T(s)-T(b) observed is up to 25 °C, an order of magnitude larger than the temperature range of SF monolayers on the surface of pure alkane melts. The measured (n,T) surface phase diagram is accounted for well by a model based on mixtures' theory, which includes an interchange energy term ω. ω is found to be negative, implying attraction between unlike species, rather than the repulsion found for SF of binary alkane mixtures. Thus, the surfactant/alkane mixing is a necessary condition for the occurrence of SF in these LG films. The X-ray derived structure of the films is presented in an accompanying paper.