A new regional hypocenter location method is presented in this article to address location problems associated with sparse station distributions and lack of velocity information. For an arbitrary slowness structure, an unknown parameter, slowness deviation, is introduced to construct a more precise slowness model than a homogeneous slowness model. By incorporating a genetic algorithm, the new method yields reasonable solutions for epicenters and origin times both inside and outside the seismic network. The synthetic data tests indicate that outside the network the new method gives excellent results for epicenter locations compared with Geiger's method, even when Geiger's method is used with the true velocity structure. The relocation of the Loma Prieta mainshock and 26 aftershocks occurring within the first 24 h after the mainshock by using the new hypocenter location method places the aftershocks an average of 2.29 km to the southwest of the locations published by the Northern California Earthquake Data Center. The new locations are in better agreement with the geodetic measurements.