Polyketide and nonribosomal peptides constitute important classes of small molecule natural products. Due to the proven biological activities of these compounds, novel methods for discovery and study of the polyketide synthase (PKS) and nonribosomal peptide synthetase (NRPS) enzymes responsible for their production remains an area of intense interest, and proteomic approaches represent a relatively unexplored avenue. While these enzymes may be distinguished from the proteomic milieu by their use of the 4'-phosphopantetheine (PPant) post-translational modification, proteomic detection of PPant peptides is hindered by their low abundance and labile nature which leaves them unassigned using traditional database searching. Here we address key experimental and computational challenges to facilitate practical discovery of this important post-translational modification during shotgun proteomics analysis using low-resolution ion-trap mass spectrometers. Activity-based enrichment maximizes MS input of PKS/NRPS peptides, while targeted fragmentation detects putative PPant active sites. An improved data analysis pipeline allows experimental identification and validation of these PPant peptides directly from MS² data. Finally, a machine learning approach is developed to directly detect PPant peptides from only MS² fragmentation data. By providing new methods for analysis of an often cryptic post-translational modification, these methods represent a first step toward the study of natural product biosynthesis in proteomic settings.