Seismic ray tracing with a path-bending method leads to a nonlinear system that has much stronger nonlinearity in anisotropic media than the counterpart in isotropic media. Any path perturbation causes changes to directional velocities, which depend not only upon the spatial position but also upon the local propagation direction in anisotropic media. To combat the high nonlinearity of the problem, the Newton-type iterative algorithm is modified by enforcing Fermat’s minimum-time principle as a constraint for the solution update, instead of conventional error minimization in the nonlinear system. As the algebraic problem is incorporated with the physical principle, it is able to stabilize the solution for such a highly nonlinear problem as ray tracing in realistically complicated anisotropic media. With this modified algorithm, two ray-tracing schemes are presented. The first scheme involves newly derived raypath equations, which are approximate for anisotropic media but the minimum-time constraint will ensure that the solution steadily converges to the true solution. The second scheme is based on the minimal variation principle. It is more efficient than the first one as it solves a tridiagonal system and does not need to compute the Jacobian and its inverse in each iteration. Even in this second scheme, Fermat’s minimum-time constraint is employed for the solution update, so as to guarantee a robust convergence of the iterative solution in anisotropic media.