Probabilistic earthquake location with non-linear, global-search methods allows the use of 3D models and produces comprehensive uncertainty and resolution information represented by a probability density function (PDF) over the unknown hypocentral parameters. We describe a probabilistic earthquake location methodology and introduce an efficient Metropolis-Gibbs, non-linear, global sampling algorithm to obtain such locations. Using synthetic travel times generated in a 3D model we examine the locations and uncertainties given by an exhaustive grid-search and the Metropolis-Gibbs sampler using 3D and layered velocity models, and by a iterative, linear method in the layered model. We also investigate the relation of average station residuals to know static delays in the travel times, and the quality of the recovery of known focal mechanisms. With the 3D model and exact data, the location PDFs obtained with the Metropolis-Gibbs method are nearly identical to those of the slower but exhaustive grid-search. The location PDFs can be large and irregular outside of a station network even for the case of exact data. With location in the 3D model and static shifts added to the data there are systematic biases in the event locations. Locations using the layered model show that both linear and global methods give systematic biases in the event locations and that the error volumes do not include the "true" location - absolute event locations and errors are not recovered. The iterative, linear location method can fail for locations near sharp contrasts in velocity and outside of a network. Metropolis-Gibbs is a practical method to obtain complete, probabilistic locations for large numbers of events and for location in 3D models. It is only about 10 times slower than linearised methods but is stable for cases where linearised methods fail. The exhaustive grid-search method is about 1000 times slower than linearised methods but is useful for location of smaller number of events and to obtain accurate images of location P DFs that may be highly-irregular.