The efficiency of any inversion method for estimating the medium parameters from seismic data strongly depends on simulation of the wave propagation, i.e., forward modeling. The requirements are that it should be accurate, fast, and computationally efficient. When the inversion is carried out in the frequency domain (FD), e.g., FD full-waveform inversion, only a few monochromatic components are involved in the computations. In this situation, FD forward modeling is an appealing potential alternative to conventional time-domain solvers. Iterative FD solvers, based on a Krylov subspace iterative method, are of interest due to their moderate memory requirements compared with direct solvers. A huge issue preventing their successful use is a very slow convergence. We have developed an iterative solver for the elastic wave propagation in 3D isotropic heterogeneous land models. Its main ingredient is a novel preconditioner, which provides the convergence of the iteration. We have developed and justified a method to invert our preconditioner effectively on the base of the 2D fast Fourier transform and solving a system of linear algebraic equations with a banded matrix. In addition, we determine how to parallelize our solver using the conventional hybrid parallelization (MPI in conjunction with OpenMP) and demonstrate the good scalability for the widespread 3D SEG/EAGE overthrust model. We find that our method has a high potential for low-frequency simulations in land models with moderate lateral variations and arbitrary vertical variations.