Abstract An approach for calculating first-arrival traveltimes in a transversely isotropic medium is developed and has the advantage of avoiding shadow zones while still being computationally fast. Also, it works with an arbitrary velocity grid that may have discontinuities. The method is based on Fermat's principle. The traveltime for each point in the grid is calculated several times using previously calculated traveltimes at surrounding grid points until the minimum time is found. Different ranges of propagation angle are covered in each traveltime calculation such that at the end of the process all propagation angles are covered. This guarantees that the first-arrival traveltime for a specific grid point is correctly calculated. The resulting algorithm is fully vectorizable. The method is robust and can accurately determine first-arrival traveltimes in heterogeneous media. Traveltimes are compared to finite-difference modeling of transversely isotropic media and are found to be in excellent agreement. An application to prestack migration is used to illustrate the usefulness of the method.