Food allergy is a growing health problem worldwide; thus, there is an urgent need for robust, specific, and sensitive analytical methods for detecting allergens. Mass spectrometry is an alternative to the existing methods, and it can overcome their limitations. One of the first steps in the development of any analytical method is the identification of the analytes to be further studied. In the case of allergen detection by mass spectrometry, the analytes are peptides. In this study, a strategy was developed for identifying potential peptide biomarkers in processed food products. This strategy was applied to processed egg matrices, and 16 potential peptide biomarkers were identified for the further detection and quantification of egg by means of mass spectrometry. With an empirical approach based on dedicated sample preparation, including tandem Lys-C/trypsin enzymatic digestion and high-resolution mass spectrometry analysis, hundreds of peptides from egg proteins were identified. This list of peptides was further refined with a series of criteria, obtained from empirical evidence, to identify the ideal biomarkers for the development of a quantitative method. These criteria include the resistance to food processing and the specificity of the peptides for eggs but also the effects of amino acid modifications and enzymatic digestion efficiency.