Shortly after mixing cement grains with water, a cementitious fluid paste is formed that immediately transforms into a solid form by a phenomenon known as setting. Setting actually corresponds to the percolation of emergent network structures consisting of dissolving cement grains glued together by nanoscale hydration products, mainly calcium-silicate-hydrates. As happens in many percolation phenomena problems, the theoretical identification of the percolation threshold (i.e. the cement setting) is still challenging, since the length scale where percolation becomes apparent (typically the length of the cement grains, microns) is many times larger than the nanoscale hydrates forming the growing spanning network. Up to now, the long-lasting gap of knowledge on the establishment of a seamless handshake between both scales has been an unsurmountable obstacle for the development of a predictive theory of setting. Herein we present a true multi-scale model which concurrently provides information at the scale of cement grains (microns) and at the scale of the nano-hydrates that emerge during cement hydration. A key feature of the model is the recognition of cement setting as an off-lattice bond percolation process between cement grains. Inasmuch as this is so, the macroscopic probability of forming bonds between cement grains can be statistically analysed in smaller local observation windows containing fewer cement grains, where the nucleation and growth of the nano-hydrates can be explicitly described using a kinetic Monte Carlo Nucleation and Growth model. The most striking result of the model is the finding that only a few links (~12%) between cement grains are needed to reach setting. This directly unveils the importance of explicitly including nano-texture on the description of setting and explains why so low amount of nano-hydrates is needed for forming a spanning network. From the simulations, it becomes evident that this low amount is least affected by processing variables like the water-to-cement ratio and the presence of large quantities of nonreactive fillers. These counter-intuitive predictions were verified by ex-professo experiments that we have carried out to check the validity of our model.