The traveltime of compressional (P) and shear (S) waves have proven essential in many applications of earthquake and exploration seismology. An accurate and efficient traveltime computation for P and S waves is crucial for the success of these applications. However, solutions to the Eikonal equation with a complex phase velocity field in anisotropic media is challenging. The Eikonal equation is a first-order, hyperbolic, nonlinear partial differential equation (PDE) that represents the high-frequency asymptotic approximation of the wave equation. The fast marching and sweeping methods are commonly used due to their efficiency in numercally solving Eikonal equation. However, these methods suffer from numerical inaccuracy in anisotropic media with sharp heterogeneity, irregular surface topography and complex phase velocity fields. This study presents a new method to solving the Eikonal equation by employing the peridynamic differential operator (PDDO). The PDDO provides the nonlocal form of the Eikonal equation by introducing an internal length parameter (horizon) and a weight function with directional nonlocality. The operator is immune to discontinuities in the form sharp changes in field or model variables and invokes the direction of traveltime in a consistent manner. The weight function controls the degree of association among points within the horizon. Solutions are constructed in a consistent manner without upwind assumptions through simple discretization. The capability of this approach is demonstrated by considering different types of Eikonal equations on complex velocity models in anisotropic media.