The canonical description is based on the prior choice of a spacelike foliation, hence making a reference to a spacetime metric. However, the metric is expected to be a dynamical, fluctuating quantity in quantum gravity. After presenting the developments in the History Projection Operator histories theory in the last seven years--giving special emphasis on the novel temporal structure of the formalism--we show how this problem can be solved in the histories formulation of general relativity. We implement the 3+1 decomposition using metric-dependent foliations which remain spacelike with respect to all possible Lorentzian metrics. This allows us to find an explicit relation of covariant and canonical quantities which preserves the spacetime character of the canonical description. In this new construction we have a coexistence of the spacetime diffeomorphisms group Diff(M) and the Dirac algebra of constraints.