The subject of this paper deals with the mathematical formulation of the Heisenberg Indeterminacy Principle in the framework of Quantum Gravity. The starting point is the establishment of the so-called time-conjugate momentum inequalities holding for non-relativistic and relativistic Quantum Mechanics. The validity of analogous Heisenberg inequalities in quantum gravity, which must be based on strictly physically observable quantities (i.e., necessarily either 4-scalar or 4-vector in nature), is shown to require the adoption of a manifestly covariant and unitary quantum theory of the gravitational field. Based on the prescription of a suitable notion of Hilbert space scalar product, the relevant Heisenberg inequalities are established. Besides the coordinate-conjugate momentum inequalities, these include a novel proper-time-conjugate extended momentum inequality. Physical implications and the connection with the deterministic limit recovering General Relativity are investigated.