The identification and localization of the proteinaceous binders are essential issues in studies of painting materials and techniques, for further proposing valid restoration and conservation treatments of the painted or polychrome works of art. The challenge for analytical chemists and conservation scientists is the availability of methods able to simultaneously identify and map the presence of the binders in the multilayered structure of a sample and the possibility to use a very low amount of sample from the studied art object (considering also the criteria of minimum sampling). These methods should be fast, reproducible in different artefacts and in case of mixture of protein-based binders with other non-proteinaceous constituents (oils, resins, waxes, gums etc.) and also economical (both in terms of materials and time consume). In this context, the present paper proposes an innovative protocol of investigation using two complementary techniques – Matrix-Assisted Laser Desorption/Ionisation – Time of Flight Mass Spectrometry (MALDI-TOF MS) and staining tests (one visible and one fluorescent stain) assisted by Optical Microscopy (OM) on cross-section of samples – for the simultaneous identification and mapping of protein – and oil-based binders in paint materials. The novelty is based on the use of MALDI-TOF MS on cross-sections of paints together with a fluorescent stain for protein identification and mapping (mainly used in the area of proteomics) complementing the use of a traditional visible stain for oil-based material identification. The protocol was successfully applied on several samples taken from a Czech medieval polychrome sculpture, entitled “The Mourning of Jesus Christ” (16th century) belonging to the Moravian Gallery (Brno).