Sensitive detection of food allergens is affected by food processing and foodstuff complexity. It is therefore a challenge to detect cross-contamination in food production that could endanger an allergic customer's life. Here we used ultra-high performance liquid chromatography coupled to tandem mass spectrometry for simultaneous detection of traces of milk (casein, whey protein), egg (yolk, white), soybean, and peanut allergens in different complex and/or heat-processed foodstuffs. The method is based on a single protocol (extraction, trypsin digestion, and purification) applicable to the different tested foodstuffs: chocolate, ice cream, tomato sauce, and processed cookies. The determined limits of quantitation, expressed in total milk, egg, peanut, or soy proteins (and not soluble proteins) per kilogram of food, are: 0.5mg/kg for milk (detection of caseins), 5mg/kg for milk (detection of whey), 2.5mg/kg for peanut, 5mg/kg for soy, 3.4mg/kg for egg (detection of egg white), and 30.8mg/kg for egg (detection of egg yolk). The main advantage is the ability of the method to detect four major food allergens simultaneously in processed and complex matrices with very high sensitivity and specificity.