The dynamics of a proteome can only be addressed with large-scale, high-throughput methods. To cope with the inherent complexity, techniques based on targeted quantification using proteotypic peptides are arising. This is an essential systems biology approach; however, for the exploratory discovery of unexpected markers, nontargeted detection of proteins, and protein modifications is indispensable. We present a rapid label-free shotgun proteomics approach that extracts relevant phenotype-specific peptide product ion spectra in an automated workflow without prior identification. These product ion spectra are subsequently sequenced with database search and de novo prediction algorithms. We analyzed six potato tuber cultivars grown on three plots of two geographically separated fields in Germany. For data mining about 1.5 million spectra from 107 analyses were aligned and statistically examined in approximately 1 day. Several cultivar-specific protein markers were detected. Based on de novo-sequencing a dominant protein polymorphism not detectable in the available EST-databases was assigned exclusively to a specific potato cultivar. The approach is applicable to organisms with unsequenced or incomplete genomes and to the automated extraction of relevant mass spectra that potentially cannot be identified by genome/EST-based search algorithms.