Abstract Motivation The neighbor-joining (NJ) algorithm is a widely used method to perform iterative clustering and forms the basis for phylogenetic reconstruction in several bioinformatic pipelines. Although NJ is considered to be a computationally efficient algorithm, it does not scale well for datasets exceeding several thousand taxa (>100 000). Optimizations to the canonical NJ algorithm have been proposed; these optimizations are, however, achieved through approximations or extensive memory usage, which is not feasible for large datasets. Results In this article, two new algorithms, dynamic neighbor joining (DNJ) and heuristic neighbor joining (HNJ), are presented, which optimize the canonical NJ method to scale to millions of taxa without increasing the memory requirements. Both DNJ and HNJ outperform the current gold standard methods to construct NJ trees, while DNJ is guaranteed to produce exact NJ trees. Availability and implementation https://bitbucket.org/genomicepidemiology/ccphylo.git Supplementary information Supplementary data are available at Bioinformatics online.