A deformation of the algebra of diffeomorphisms is constructed for canonically deformed spaces with constant deformation parameter theta. The algebraic relations remain the same, whereas the comultiplication rule (Leibniz rule) is different from the undeformed one. Based on this deformed algebra a covariant tensor calculus is constructed and all the concepts like metric, covariant derivatives, curvature and torsion can be defined on the deformed space as well. The construction of these geometric quantities is presented in detail. This leads to an action invariant under the deformed diffeomorphism algebra and can be interpreted as a theta-deformed Einstein-Hilbert action. The metric or the vierbein field will be the dynamical variable as they are in the undeformed theory. The action and all relevant quantities are expanded up to second order in theta.