Undertaking the conservation of artworks informed by the results of molecular analyses has gained growing importance over the last decades, and today it can take advantage of state-of-the-art analytical techniques, such as mass spectrometry-based proteomics. Protein-based binders are among the most common organic materials used in artworks, having been used in their production for centuries. However, the applications of proteomics to these materials are still limited. In this work, a palaeoproteomic workflow was successfully tested on paint reconstructions, and subsequently applied to micro-samples from a 15th-century panel painting, attributed to the workshop of Sandro Botticelli. This method allowed the confident identification of the protein-based binders and their biological origin, as well as the discrimination of the binder used in the ground and paint layers of the painting. These results show that the approach is accurate, highly sensitive, and broadly applicable in the cultural heritage field, due to the limited amount of starting material required. Accordingly, a set of guidelines are suggested, covering the main steps of the data analysis and interpretation of protein sequencing results, optimised for artworks.