The search for shortest paths is an essential primitive for a variety of graph-based applications, particularly those on online social networks. For example, LinkedIn users perform queries to find the shortest path “social links” connecting them to a particular user to facilitate introductions. This type of graph query is challenging for moderately sized graphs, but becomes computationally intractable for graphs underlying today’s social networks, most of which contain millions of nodes and billions of edges. We propose Atlas, a novel approach to scalably approximate shortest paths between graph nodes using a collection of spanning trees. Spanning trees are easy to generate, compact relative to original graphs, and can be distributed across machines to parallelize queries. We demonstrate its scalability and effectiveness using 6 large social graphs from Facebook, Orkut and Renren, the largest of which includes 43 million nodes and 1 billion edges. We describe techniques to incrementally update Atlas as social graphs change over time. We capture graph dynamics using 35 daily snapshots of a Facebook network, and show that Atlas can amortize the cost of tree updates over time. Finally, we apply Atlas to several graph applications, and show that they produce results that closely approximate ideal results.