The interaction of water with metal oxides controls their activity and stability in heterogeneous catalysis and electrocatalysis. In this work, we combine density functional theory calculations and infrared reflection absorption spectroscopy (IRAS) to identify the structural motifs formed upon interaction of water with an atomically defined Co₃O₄(111) surface. Three principal structures are observed: (i) strongly bound isolated OD, (ii) extended hydrogen-bonded OD/D₂O structures, and (iii) a third structure which has not been reported to our knowledge. In this structure, surface Co²⁺ ions bind to three D₂O molecules to form an octahedrally coordinated Co²⁺ with a "half hydration shell". We propose that this hydration structure represents an important intermediate in reorganization and dissolution on oxide surfaces which expose highly unsaturated surface cations.