The early stages of corrosion occurring at liquid-solid interfaces control the evolution of the material's degradation process, yet due to their transient state, their analysis remains a formidable challenge. Here corrosion tests are performed on a MgCa alloy, a candidate material for biodegradable implants using pure water as a model system. The corrosion reaction is suspended by plunge freezing into liquid nitrogen. The evolution of the early-stage corrosion process on the nanoscale by correlating cryo-atom probe tomography (APT) with transmission-electron microscopy (TEM) and spectroscopy, is studied. The outward growth of Mg hydroxide Mg(OH)2 and the inward growth of an intermediate corrosion layer consisting of hydrloxides of different compositions, mostly monohydroxide Mg(OH) instead of the expected MgO layer, are observed. In addition, Ca partitions to these newly formed hydroxides and oxides. Density-functional theory calculations suggest a domain of stability for this previously experimental unreported Mg(OH) phase. This new approach and these new findings advance the understanding of the early stages of magnesium corrosion, and in general reactions and processes at liquid-solid interfaces, which can further facilitate the development of corrosion-resistant materials or better control of the biodegradation rate of future implants.