We develop a regional seismic travel-time (RSTT) model and method for use in routine seismic analysis. The model parameterization is a global tessellation of nodes with a velocity profile at each node. Interpolation of the velocity profiles generates a 3D crust and laterally variable upper-mantle velocity. The upper-mantle velocity profile at each node is represented as a linear velocity gradient, which enables travel-time computation in approximately 1 millisecond. This computational speed allows the model to be used in routine analyses in operational monitoring systems. We refine the model using a tomographic formulation that adjusts the average crustal velocity, mantle velocity at the Moho, and the mantle velocity gradient at each node. While the RSTT model is inherently global, our first RSTT tomographic effort covers Eurasia and North Africa, where we have compiled a data set of approximately 600,000 Pn arrivals. Ten percent of the data set is randomly selected and set aside for testing purposes. Travel-time residual variance for the validation data is reduced by 32%. Based on a geographically distributed set of validation events with epicenter accuracy of 5 km or better, epicenter error using 16 Pn arrivals is reduced by 46% from 17.3 km (ak135 model) to 9.3 km (RSTT model) after tomography. The median uncertainty ellipse area is reduced by 68% from 3070 km2 (ak135) to 994 km2 (RSTT), and the number of ellipses with area less than 1000 km2, which is the area allowed for onsite inspection under the Comprehensive Nuclear Test Ban Treaty, is increased from 0% (ak135) to 51% (RSTT).