Egg-tempera painting is a pictorial technique widely used in the Middle Ages, although poorly studied in its physico-chemical aspects until now. Here we show how NMR relaxometry and rheology can be combined to probe egg-tempera paints and shed new light on their structure and behavior. Based on recipes of the 15th century, model formulations with egg yolk and green earth have been reproduced to characterize the physicochemical properties of this paint at the mesoscopic and macroscopic scales. The rheological measurements highlight a synergetic effect between green earth and egg yolk, induced by the interactions between them and the structural organisation of the system. 1H NMR relaxometry emphasizes the presence and the structure of a network formed by the yolk and the pigment.