The red shades of 13 icons (15th-17th century) of the Cretan School of iconography are investigated in detail to identify the inorganic and organic colouring materials comprising the paint layers. Examination of sample cross-sections is performed with optical microscopy. Micro-Raman spectroscopy and high performance liquid chromatography (HPLC) coupled to a photodiode array detector are employed for the identification of the inorganic and organic colouring materials, respectively. The results reveal the extensive use of coccid dyes by the Cretan painters: kermes (Kermes vermilio Planchon) is found in icons dated before the middle 16th century and cochineal in icons created several decades after the discovery of the New World. Other dyestuffs detected in the historical samples are madder (possibly Rubia tinctorum L., according to HPLC profiles), soluble redwood and indigoid dyes. Organic dyes were used by the painters as exclusive colouring matters (or glazes) or in mixtures with inorganic pigments, such as red ochre, cinnabar, minium, azurite lead white and carbon black. Liquid chromatography with mass spectrometry (LC-MS) coupled to a negative electrospray ionization mode is employed to provide information on the identity of some unknown colouring components, of the aforementioned dyes, detected in the historical samples. The results suggest that (i) the type B compound (also known as Bra') is a dehydro-brazilein product and (ii) the deprotonated molecular ion of the type C compound corresponds to m/z - 243. Both compounds are commonly used as markers for the identification of soluble redwood in historical samples. LC-MS analysis of cochineal shows that the dcIV and dcVII components are isomeric with carminic acid, as it has been recently suggested. Finally, LC-MS is employed to identify and record kermesic and flavokermesic acid in kermes and rubiadin in wild madder.