  We analyze the application of the history state formalism to quantum walks.
The formalism allows one to describe the whole walk through a pure quantum
history state, which can be derived from a timeless eigenvalue equation. It
naturally leads to the notion of system-time entanglement of the walk, which
can be considered as a measure of the number of orthogonal states visited in
the walk. We then focus on one-dimensional discrete quantum walks, where it is
shown that such entanglement is independent of the initial spin orientation for
real Hadamard-type coin operators and real initial states (in the standard
basis) with definite site parity. Moreover, in the case of an initially
localized particle it can be identified with the entanglement of the unitary
global operator that generates the whole history state, which is related to its
entangling power and can be analytically evaluated. Besides, it is shown that
the evolution of the spin subsystem can also be described through a spin
history state with an extended clock. A connection between its average
entanglement (over all initial states) and that of the operator generating this
state is also derived. A quantum circuit for generating the quantum walk
history state is provided as well.
