We suggest, that Einstein gravity is self-complete in deep UV, but in the sense very different from conventional Wilsonian completion. We discuss some consequences of this phenomenon. In particular, the volumes of compactified spaces as well as the areas of black hole horizons must be quantized in Planck units. This quantization has phenomenological consequences, most dramatic being for micro black holes in theories with TeV scale gravity that may be accessible at LHC. We predict, that black holes come in form of a discrete tower with well defined spacing. Instead of thermal evaporation, they decay through the sequence of spontaneous particle emissions, with each transition reducing the horizon area by strictly integer number of Planck units. We also discuss some cosmological implications. Quantization of the horizons can be a crucial missing link by which the notion of the minimal length in gravity eliminates physical singularities.