Combining the quantum scale invariance with the absence of new degrees of freedom above the electroweak scale leads to stability of the latter against perturbative quantum corrections. Nevertheless, the hierarchy between the weak and the Planck scales remains unexplained. We argue that this hierarchy can be generated by a non-perturbative effect relating the low energy and the Planck-scale physics. The effect is manifested in the existence of an instanton configuration contributing to the vacuum expectation value of the Higgs field. We analyze such configurations in several toy models and in a phenomenologically viable theory encompassing the Standard Model and General Relativity in a scale-invariant way. Dynamical gravity and a non-minimal coupling of it to the Higgs field play a crucial role in the mechanism.