Natural products (NPs) are a rich source of medicines, but traditional discovery methods are often unsuccessful due to high rates of rediscovery. Genetic approaches for NP discovery are promising, but progress has been slow due to the difficulty of identifying unique biosynthetic gene clusters (BGCs) and poor gene expression. We previously developed the metabologenomics method, which combines genomic and metabolomic data to discover new NPs and their BGCs. Here, we utilize metabologenomics in combination with molecular networking to discover a novel class of NPs, the tyrobetaines: nonribosomal peptides with an unusual trimethylammonium tyrosine residue. The BGC for this unusual class of compounds was identified using metabologenomics and computational structure prediction data. Heterologous expression confirmed the BGC and suggests an unusual mechanism for trimethylammonium formation. Overall, the discovery of the tyrobetaines shows the great potential of metabologenomics combined with molecular networking and computational structure prediction for identifying interesting biosynthetic reactions and novel NPs.