This work describes the application of infrared spectroscopy combined with chemometric tools for the characterization of the proteinaceous binding media used in medieval paints. Historically accurate reconstructions of the most common binders and binder mixtures used in medieval illuminations (egg white, egg yolk, parchment glue and casein glue) were made. Red and blue colors based on vermilion and lapis lazuli were selected as reference paint samples. These two colors were very widely used in medieval illuminations. Different chemometrics methods (supervised and unsupervised), applied to infrared spectral data, were evaluated in terms of their accuracy in the characterization and quantification of complex binding media formulations of the red and blue paints. Principal components analysis and hierarchical cluster analysis revealed that the C\H stretching absorption region (3000–2840 cm−1) and the ester-amides region (1760–1495 cm−1) were the best wavenumber region for discriminating the different proteinaceous binders. A regression analysis using classical least squares and partial least squares regression allowed the quantification of binder composition in red and blue paint reconstructions. The restriction to the ester-amide absorption region presented the best spectral reconstruction error and the lowest binder composition reconstruction error.