The purpose of the present work is to quantify the correlation structure of simulated velocity fields in heterogeneous permeability fields and to discuss how to represent it in upscaled transport models. We investigate the velocity field correlation structure for multinormal log permeability fields. The simulated velocity distributions are analyzed in a Lagrangian framework, i.e., along the particles' paths. To quantify the different spatial organization of low- and high-velocity zones, we condition the estimated velocity correlation length and time on the initial particle velocity. The velocity correlation length is found to increase with the initial particle velocity, following a power law. Such an effect is likely due to the channeling of high-velocity zones, which implies that particles keep memory of their initial velocity over longer distances for high initial velocities than for low initial velocities. Two distinct regimes are identified for the velocity correlation time. For low initial particle velocity the correlation time is controlled by the large time needed to escape from the low-velocity zones. For high initial particle velocity it is controlled by the large time needed for particles to sample the whole velocity field, in particular low-velocity zones. One of the consequences of these results is that for such velocity fields the nonlinear dependence of both the correlation length and time on the particle initial velocity restricts the use of spatial or temporal Markovian assumptions for modeling velocity transitions in effective transport models.