We introduce a new method for determining earthquake focal mechanisms from P-wave first-motion polarities. Our technique differs from previous methods in that it accounts for possible errors in the assumed earthquake location and seismic-velocity model, as well as in the polarity observations. The set of acceptable focal mechanisms, allowing for the expected errors in polarities and takeoff angles, is found for each event. Multiple trials are performed with different source locations and velocity models, and mechanisms with up to a specified fraction of misfit polarities are included in the set of acceptable mechanisms. The average of the set is returned as the preferred mechanism, and the uncertainty is represented by the distribution of acceptable mechanisms. The solution is considered adequately stable only if the set of acceptable mechanisms is tightly clustered around the preferred mechanism. We validate the method by demonstrating that the well-constrained mechanisms found for clusters of closely spaced events with similar waveforms are indeed very similar. Tests on noisy synthetic data, which mimic the event and station coverage of real data, show that the method accurately recovers the mechanisms and that the uncertainty estimates are reasonable. We also investigate the sensitivity of focal mechanisms to changes in polarities, event depth, and seismic-velocity model, and we find that mechanisms are most sensitive to changes in the vertical velocity gradient.