Studies of the structure of supported water clusters provide a means for obtaining a rigorous molecular-scale description of the initial stages of heterogeneous ice nucleation: a process of importance to fields as diverse as atmospheric chemistry, astrophysics and biology. Here, we report the observation and characterization of metal-supported water hexamers and a family of hydrated nanoclusters--heptamers, octamers and nonamers--through a combination of low-temperature scanning tunnelling microscopy experiments and first-principles electronic-structure calculations. Aside from achieving unprecedented resolution of the cyclic water hexamer--the so-called smallest piece of ice--we identify and explain a hitherto unknown competition between the ability of water molecules to simultaneously bond to a substrate and to accept hydrogen bonds. This competition also rationalizes previous structure predictions for water clusters on other substrates.