In this paper we establish Riemann-Roch and Lefschtez-Riemann-Roch theorems for arbitrary proper maps of finite cohomological dimension between algebraic DG-stacks for which coarse-moduli-spaces exist as quasi-projective schemes over a Noetherian excellent base scheme. (Observe that this includes also Artin stacks with finite diagonal.) The Riemann-Roch theorem is established as a natural transformation between the G-theory of algebraic stacks and Bredon-style homology theories for stacks defined in our earlier work. The Lefschtez-Riemann-Roch is an extension of this including the action of tori. Applications include various formulae for virtual fundamental classes for moduli stacks of stable curves which are discussed in detail in the sequel to this paper.