Cement is one of the most produced materials in the world. A major player in greenhouse gas emissions, it is the main binding agent in concrete, to which it provides a cohesive strength that rapidly increases during setting. Understanding how such cohesion emerges has been a major obstacle to advances in cement science and technology. Here, we combine computational statistical mechanics and theory to demonstrate how cement cohesion results from the organization of interlocked ions and water, progressively confined in nano-slits between charged surfaces of Calcium-Silicate-Hydrates. Due to the water/ions interlocking, dielectric screening is drastically reduced and ionic correlations are proven significantly stronger than previously thought, dictating the evolution of the nano-scale interactions during cement hydration. By developing a quantitative analytical prediction of cement cohesion based on Coulombic forces, we reconcile a novel fundamental understanding of cement hydration with the fully atomistic description of the solid cement paste and open new paths for science and technologies of construction materials.