ABSTRACT Tens of thousands of biosynthetic gene clusters (BGCs) have been identified in microbial genomes, but the vast majority of associated natural products (NPs) and their underlying biosyntheses remain unknown. Metabologenomics approaches integrate genomic and metabolomic datasets to statistically associate BGCs to their cognate NPs, yet often suggest many false links. Here, we show that incorporating information on the producer strains' phylogeny greatly improves accuracy. We sequenced 72 Sorangium spp. genomes (myxobacteria), predicting 2030 BGCs in 265 gene cluster families (GCFs). Mass spectrometry (MS 1 ) revealed 99 metabolite families (MFs) from the same strains. Using a phylogeny‐aware statistical analysis, we identified 43 high‐confidence associations between GCFs and MFs, correctly including 89% of previously characterised links and reducing spurious associations by 33‐fold, compared to simple correlational analysis. Our approach identified previously unknown BGCs for rowithocin and an undescribed poly‐glycosylated NP. It also identified a distinct BGC associated with the production of chlorotonil C variants and refined the BGC for maracen. This study demonstrates the effectiveness of phylogeny‐aware metabologenomics as a scalable strategy for NP discovery and biosynthetic pathway elucidation, and provides a roadmap to improved analyses of paired‐omics data towards NP discovery.