Computing first-arrival traveltimes in the presence of anisotropy is important for high-end near surface modeling, microseismic source localization, and fractured reservoir characterization. Anisotropy deviating from elliptical anisotropy introduces higher-order nonlinearity into the eikonal equation, which makes solving the equation a challenging task. We address this challenge by iteratively solving a sequence of simpler tilted elliptically anisotropic eikonal equations. At each iteration, the source function is updated to capture the effects due to the higher order nonlinear terms in the anisotropy. We use Aitken extrapolation to speed up the convergence rate of the iterative algorithm. The result is an efficient algorithm for firstarrival traveltime computations in tilted anisotropic media. We demonstrate the proposed method for the tilted transversely isotropic media and the tilted orthorhombic media. Numerical tests show that the proposed method is feasible and produces results that are comparable to wavefield extrapolation, even for strongly anisotropic and complex structures. Therefore, for the cases where one or two-point ray tracing fails, our method may be a potential substitute for computing traveltimes.