We introduce the Quantum Holonomy-Diffeomorphism *-algebra, which is generated by holonomy-diffeomorphisms on a 3-dimensional manifold and translations on a space of SU(2)-connections. We show that this algebra encodes the canonical commutation relations of canonical quantum gravity formulated in terms of Ashtekar variables. Furthermore, we show that semi-classical states exist on the holonomy-diffeomorphism part of the algebra but that these states cannot be extended to the full algebra. Via a Dirac type operator we derive a certain class of unbounded operators that act in the GNS construction of the semi-classical states. These unbounded operators are the type of operators, which we have previously shown to entail the spatial 3-dimensional Dirac operator and Dirac Hamiltonian in a semi-classical limit. Finally, we show that the structure of the Hamilton constraint emerges from a Yang-Mills type operator over the space of SU(2)-connections.