The reactivity of calcite, one of the most abundant minerals in the earth's crust, is determined by the molecular details of its interface with the contacting solution. Recently, it has been found that trace concentrations of NaNO3 severely affect calcite's (104) surface and its reactivity. Here we combine molecular dynamics (MD) simulations, X-ray reflectivity (XR) and in situ atomic force microscopy (AFM) to probe the calcite (104) - water interface in the presence of NaNO3. Simulations reveal density profiles of different ions near calcite's surface, with NO3 - able to reach closer to the surface than CO3 2- and in higher concentrations. Reflectivity measurements show a structural destabilisation of the (104) surfaces' topmost atomic layers in NaNO3 bearing solution, with distorted rotation angles of the carbonate groups and substantial displacement of the lattice ions. Nanoscale AFM results confirm the alteration of crystallographic characteristics, and the ability of dissolved NaNO3 to modify the structure of interfacial water was observed by AFM force spectroscopy. Our experiments and simulations consistently evidence a dramatic deterioration of the crystals' surface, with potentially important implications for geological and industrial processes.