We present a new approach to determine precise and reliable hypocenter locations in the tectonically complex region of Switzerland. A three-dimensional (3-D) P wave velocity model to be used for earthquake relocation is obtained by simultaneously inverting arrival times of local earthquakes for hypocenter locations and 3-D P wave velocity structure. A 3-D P wave velocity model derived from controlled source seismology (CSS) is used as an initial reference model. The final 3-D model thus combines all available information from both CSS and local earthquake data. The probabilistic, nonlinear formulation of the earthquake location problem includes a complete description of location uncertainties and can be used with any kind of velocity model. In particular, the combination of nonlinear, global search algorithms, such as the Oct-Tree Importance Sampling, with probabilistic earthquake location provides a fast and reliable tool for earthquake location. The comparison of hypocenter locations obtained routinely by the Swiss Seismological Service (SED) to those relocated in the new 3-D velocity model using a probabilistic approach reveals no systematic shifts but does exhibit large individual shifts in some epicenter locations and focal depths. We can attribute these large shifts in part to large uncertainties in the hypocenter location. Events with a low number of observations (<8) and no observation within the critical focal depth distance typically show large location uncertainties. Improved hypocentral locations, particularly for mine blasts and earthquakes whose routine hypocenter locations had been questionable, confirm that improved velocity model and probabilistic earthquake location yield more precise and reliable hypocenter locations and associated location uncertainties for Switzerland.