Summary: The deformation of elementary fluid volumes by velocity gradients is a key process for scalar mixing, chemical reactions and biological processes in flows. Whilst fluid deformation in unsteady, turbulent flow has gained much attention over the past half-century, deformation in steady random flows with complex structure – such as flow through heterogeneous porous media – has received significantly less attention. In contrast to turbulent flow, the steady nature of these flows constrains fluid deformation to be anisotropic with respect to the fluid velocity, with significant implications for e.g. longitudinal and transverse mixing and dispersion. In this study we derive an ab initio coupled continuous-time random walk (CTRW) model of fluid deformation in random steady three-dimensional flow that is based upon a streamline coordinate transform which renders the velocity gradient and fluid deformation tensors upper triangular. We apply this coupled CTRW model to several model flows and find that these exhibit a remarkably simple deformation structure in the streamline coordinate frame, facilitating solution of the stochastic deformation tensor components. These results show that the evolution of longitudinal and transverse fluid deformation for chaotic flows is governed by both the Lyapunov exponent and power-law exponent of the velocity probability distribution function at small velocities, whereas algebraic deformation in non-chaotic flows arises from the intermittency of shear events following similar dynamics as that for steady two-dimensional flow.