The article discusses the prospects for using the neighbor-joining (NJ) method to infer very large phylogenies, which are increasingly important in molecular evolution and functional genomics. The NJ method is widely used due to its accuracy for smaller data sets and computational speed, but it examines only a small fraction of the possible tree topologies for large data sets. The authors present a likelihood method for simultaneously estimating all pairwise distances using biologically realistic models of nucleotide substitution, which corrects up to 60% of NJ tree errors. Computer simulations show that the accuracy of NJ trees declines only by about 5% when the number of sequences increases from 32 to 4,096, even in the presence of extensive variation in evolutionary rates or biases in nucleotide composition. The results encourage the use of complex models of nucleotide substitution for estimating evolutionary distances and suggest that the NJ method can be effectively applied to large phylogenies.The article discusses the prospects for using the neighbor-joining (NJ) method to infer very large phylogenies, which are increasingly important in molecular evolution and functional genomics. The NJ method is widely used due to its accuracy for smaller data sets and computational speed, but it examines only a small fraction of the possible tree topologies for large data sets. The authors present a likelihood method for simultaneously estimating all pairwise distances using biologically realistic models of nucleotide substitution, which corrects up to 60% of NJ tree errors. Computer simulations show that the accuracy of NJ trees declines only by about 5% when the number of sequences increases from 32 to 4,096, even in the presence of extensive variation in evolutionary rates or biases in nucleotide composition. The results encourage the use of complex models of nucleotide substitution for estimating evolutionary distances and suggest that the NJ method can be effectively applied to large phylogenies.