We consider the problem of recovering a set of locations given observations of the direction between pairs of these locations.   This recovery task arises from the Structure from Motion problem, in which a three-dimensional structure is sought from a collection of two-dimensional images.  In this context, the locations of cameras and structure points are to be found from Epipolar geometry and point correspondences among images.  These correspondences are often incorrect because of lighting, shadows, and the effects of perspective.  Hence, the resulting observations of relative directions contain significant outliers.  We introduce a new method for outlier-tolerant location recovery from pairwise directions.  This method, called ShapeFit, is a convex Second Order Cone Program that can be efficiently solved.  Empirically, ShapeFit can succeed on synthetic data with over 50\% corruption.  Rigorously, we prove that ShapeFit can recover a set of locations exactly when a fraction of the measurements are adversarially corrupted and when the data model is random.  On real data, an ADMM implementation of ShapeFit yields performance comparable to the state-of-the-art with an order of magnitude speed-up. Our proposed numerical framework is flexible in that it accommodates other approaches to location recovery and can be used to speed up other methods. These properties are demonstrated by extensively testing against state-of-the-art methods for location recovery on 13 large, irregular collections of images of real scenes.