We study the stability of the Electroweak (EW) vacuum in a scale-invariant extension of the Standard Model and General Relativity, known as a Higgs-Dilaton theory. The safety of the EW vacuum against possible transition towards another vacuum is a necessary condition for the model to be phenomenologically acceptable. We find that, within a wide range of parameters of the theory, the decay rate is significantly suppressed compared to that of the Standard Model. We also discuss properties of a tunneling solution that are specific to the Higgs-Dilaton theory.