A still open question is how equilibrium warming in response to increasing radiative forcing (equilibrium climate sensitivity S) is depending on background climate. We here bring paleo-data based evidence on the state-dependency of S by using CO2 proxy data together with model-based reconstruction of land ice albedo over the last 5 million years. We find that the land-ice albedo forcing depends non-linearly on the background climate, while any non-linearity of CO2 radiative forcings depends on the CO2 data set used. Over the last 2 million years the combined S_[CO2,LI] from CO2 and land-ice albedo forcing is state-dependent and during interglacials at least twice as high as during glacials, thus CO2 doubling leads to an interglacial warming of 5 K. In the Pliocene data uncertainties prevents a well-supported calculation, but our analysis suggests that S_[CO2,LI] during a land-ice free northern hemisphere was smaller than during interglacials of the Pleistocene.