Details about the molecular structures of surfactant mixtures adsorbed at the air-water interface have been controversial. Using sum frequency generation vibrational spectroscopy (SFG) and isotope labeling, we show here for the first time that mixtures of dodecanol (DOH) and sodium dodecyl sulfate (SDS) adsorb at the air-water interface with the formation of a head-to-tail complex. We observed this complex formation to occur first in the aqueous subphase, followed by complex adsorption onto the interface. This new piece of evidence for the head-to-tail complex conformation contradicts the conjectured tail-to-tail adsorption of the surfactant mixtures. The SFG data also show the dominating adsorption of the SDS-DOH complex over the single molecules of SDS and DOH at the air-water interface. The interfacial DOH-to-SDS molecular ratio of approximately 2.2:1 at a DOH-to-SDS bulk concentration ratio of 10 μM/2 mM was determined by isotope labeling of the surfactants. In addition to a smaller number of gauche defects, the DOH-SDS complex was found to adopt a higher level of orderliness than the adsorbed single surfactants. These findings provide important insights into the descriptions and interpretation of DOH-SDS adsorption at the air-water interface and its properties.