Gene tree incongruence resulting from incomplete lineage sorting (ILS) can make standard species tree estimation methods, such as concatenation, have poor accuracy. While coalescent-based methods can accurately estimate species trees in the presence of ILS, these methods can be less accurate than concatenation when estimated gene trees are insufficiently accurate. We present a new “statistical binning” technique to address this challenge: we use a statistical test for combinability and a graph-theoretic optimization to bin genes into subsets, estimate trees on each subset using concatenation, and then combine the “supergene” trees using the preferred coalescent-based method. We show that statistical binning dramatically improves the accuracy of MP-EST, a leading coalescent-based method, and we use statistical binning to produce the first genome-scale coalescent-based avian tree of life.