The neighbor-joining algorithm is a popular distance-based tree construction algorithm, but its O(n^3) runtime makes it prohibitively slow for many analyses that involve large numbers of taxa. We have developed an algorithm that creates neighbor-joining trees, but with typical runtimes far better than n^3. We describe the algorithm, empirically demonstrate its correctness for additive distances, and compare performance to other publicly available neighbor-joining implemenations.