The problem of time in canonical quantum gravity is related to the fact that 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. 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 also have a coexistence of the spacetime diffeomorphisms group, and the Dirac algebra of constraints.