We present a series of colour evolution models for Luminous Red Galaxies (LRGs) in the 7th spectroscopic data release of the Sloan Digital Sky Survey (SDSS), computed using the full-spectrum fitting code VESPA on high signal-to-noise stacked spectra. The colour-evolution models are computed as a function of colour, luminosity and redshift, and we do not a-priori assume that LRGs constitute a uniform population of galaxies in terms of stellar evolution. By computing star-formation histories from the fossil record, the measured stellar evolution of the galaxies is decoupled from the surveys selection function, which also evolves with redshift. We present these evolutionary models computed using three different sets of Stellar Population Synthesis (SPS) codes. We show that the traditional fiducial model of purely passive stellar evolution of LRGs is broadly correct, but it is not sufficient to explain the full spectral signature. We also find that higher-order corrections to this model are dependent on the SPS used, particularly when calculating the amount of recent star formation. The amount of young stars can be non-negligible in some cases, and has important implications for the interpretation of the number density of LRGs within the selection box as a function of redshift. Dust extinction, however, is more robust to the SPS modelling: extinction increases with decreasing luminosity, increasing redshift, and increasing r-i colour. We are making the colour evolution tracks publicly available at http://www.icg.port.ac.uk/~tojeiror/lrg_evolution/.