At the interface with solids, the mobility of liquid molecules tends to be reduced compared with bulk, often resulting in increased local order due to interactions with the surface of the solid. At room temperature, liquids such as water and methanol can form solvation structures, but the molecules remain highly mobile, thus preventing the formation of long-lived supramolecular assemblies. Here we show that mixtures of water with methanol can form a novel type of interfaces with hydrophobic solids. Combining in situ atomic force microscopy and multiscale molecular dynamics simulations, we identify solid-like two-dimensional interfacial structures that nucleate thermally, and are held together by an extended network of hydrogen bonds. On graphite, nucleation occurs above similar to 35 degrees C, resulting in robust, multilayered nanoscopic patterns. Our findings could have an impact on many fields where water-alcohol mixtures play an important role such as fuel cells, chemical synthesis, self-assembly, catalysis and surface treatments.