Characterizing the seismicity of Novaya Zemlya and the surrounding Arctic seas requires accurate event‐location estimates. Low‐magnitude events in this region are currently observed only by a small number of stations in the European Arctic, with a large azimuthal gap, making the accuracy of regional velocity models all the more important. Regional travel‐time calibration is difficult given the scarcity of sufficiently well‐constrained events. On 11 October 2010, a magnitude 4.5 event occurred close to the northern tip of Novaya Zemlya. This event is significant in that it is the first event in this region to have been recorded both on the relatively recent regional networks and arrays, and also teleseismically with good azimuthal coverage. We examine how well we can constrain the location and origin time using only teleseismic phases. Using only first teleseismic P arrivals, we constrain the epicenter to approximately 76.25° N and 64.75° E but with no depth resolution. Clear depth phases, notably on stations in the southern United States, indicate a depth between 9 and 15 km. This independent hypocenter and origin time estimate allow evaluation of regional phase travel‐time prediction using different models. The predicted Sn travel time appears to cause the greatest variability in regional location estimates. The 3D Regional Seismic Travel Times models provide excellent Pn travel‐time estimates for Barents Sea paths but may slightly overestimate Sn travel times from this source region. A modified regional 1D velocity model is defined, which best predicts Pn and Sn observations at multiple stations up to 15°. The significance of the regional travel‐time models for estimating location is demonstrated for a low‐magnitude event on or close to the northern island of Novaya Zemlya in March 2014, recorded with a satisfactory signal‐to‐noise ratio at only four stations.