We develop a continuous time random walk (CTRW) approach for the evolution of Lagrangian velocities in steady heterogeneous flows based on a stochastic relaxation process for the streamwise particle velocities. This approach describes the persistence of velocities over a characteristic spatial scale, unlike classical random walk methods, which model the persistence over a characteristic time scale. We first establish the relation between Eulerian and Lagrangian velocities for both equidistant and isochrone sampling along streamlines, under transient and stationary conditions. Based on this, we develop a space-continuous CTRW approach for the spatial and temporal dynamics of Lagrangian velocities. While classical CTRW formulations have nonstationary Lagrangian velocity statistics, the proposed approach quantifies the evolution of the Lagrangian velocity statistics under both stationary and nonstationary conditions. We provide explicit expressions for the Lagrangian velocity statistics and determine the behaviors of the mean particle velocity, velocity covariance, and particle dispersion. We find strong Lagrangian correlation and anomalous dispersion for velocity distributions that are tailed toward low velocities as well as marked differences depending on the initial conditions. The developed CTRW approach predicts the Lagrangian particle dynamics from an arbitrary initial condition based on the Eulerian velocity distribution and a characteristic correlation scale.