The unintentional presence of even trace amounts of certain foods constitutes a major hazard for those who suffer from food allergies. For many food industries, product and raw ingredient surveillance forms part of their risk assessment procedures. This may require the detection of multiple allergens in a wide variety of matrices. Mass spectrometry offers a possible solution for the quantification of multiple allergens in a single analysis. The capability of MS to quantify many peptides from a complex protein digestion is well known. However, a lack of matrix certified reference materials has made the optimisation of extraction and digestion conditions for multiplexed allergen quantification difficult to assess. Here, we report a systematic study, using preliminary screening followed by a Design of Experiments approach, to find the optimal buffer and digestion conditions for detecting milk and egg protein markers in a model processed food matrix. Five of the most commonly used buffers, two chaotropic reagents and two reducing reagents were assessed for the optimal extraction of multiple protein markers. While the choice of background buffer had little impact, the use of chaotropic and reducing reagents showed significant benefits for the extraction of most proteins. A full factorial design experiment was applied to the parameters shown to have a significant impact on protein recovery. These studies suggest that a single optimal set of extraction conditions enabling the quantitative recovery of all proteins is not easily achieved. Therefore, although MS is capable of the simultaneous quantification of many peptides in a single run, greater consideration of protein extraction is required before these are applied for multiplex allergen quantification in food matrices.