Most finite-frequency traveltime tomography methods are based on the Born approximation, which requires that the scale of the velocity heterogeneity and the magnitude of the velocity perturbation should be small enough to satisfy the Born approximation. On the contrary, the Rytov approximation works well for large-scale velocity heterogeneity. Typically, the Rytov-approximation-based finite-frequency traveltime sensitivity kernel (Rytov-FFTSK) can be obtained by integrating the phase-delay sensitivity kernels with a normalized weighting function, in which the calculation of sensitivity kernels requires the numerical solution of Green’s function. However, solving the Green’s function explicitly is quite computationally demanding, especially for 3D problems. To avoid explicit calculation of the Green’s function, we show that the Rytov-FFTSK can be obtained by crosscorrelating a forward-propagated incident wavefield and reverse-propagated adjoint wavefield in the time domain. In addition, we find that the action of the Rytov-FFTSK on a model-space vector, e.g., the product of the sensitivity kernel and a vector, can be computed by calculating the inner product of two time-domain fields. Consequently, the Hessian-vector product can be computed in a matrix-free fashion (i.e., first calculate the product of the sensitivity kernel and a model-space vector and then calculate the product of the transposed sensitivity kernel and a data-space vector), without forming the Hessian matrix or the sensitivity kernels explicitly. We solve the traveltime inverse problem with the Gauss-Newton method, in which the Gauss-Newton equation is approximately solved by the conjugate gradient using our matrix-free Hessian-vector product method. An example with a perfect acquisition geometry found that our Rytov-approximation-based traveltime inversion method can produce a high-quality inversion result with a very fast convergence rate. An overthrust synthetic data test demonstrates that large- to intermediate-scale model perturbations can be recovered by diving waves if long-offset acquisition is available.