A still open question is how equilibrium warming in response to increasing radiative forcing — the specific equilibrium climate sensitivity S — is depending on background climate. We here present paleo-data based evidence on the state-dependency of S, by using CO2 proxy data together with 3-D ice-sheet model-based reconstruction of land ice albedo over the last 5 million years (Myr). We find that the land-ice albedo forcing depends non-linearly on the background climate, while any non-linearity of CO2 radiative forcing depends on the CO2 data set used. This non-linearity was in similar approaches not accounted for due to previously more simplistic approximations of land-ice albedo radiative forcing being a linear function of sea level change. Important for the non-linearity between land-ice albedo and sea level is a latitudinal dependency in ice sheet area changes. In our setup, in which the radiative forcing of CO2 and of the land-ice albedo (LI) is combined, we find a state-dependency in the calculated specific equilibrium climate sensitivity S[CO2,LI] for most of the Pleistocene (last 2.1 Myr). During Pleistocene intermediate glaciated climates and interglacial periods S[CO2 ,LI] is on average ∼ 45% larger than during Pleistocene full glacial conditions. In the Pliocene part of our analysis (2.6 − 5 Myr BP) the CO2 data uncertainties prevents a well-supported calculation for S[CO2,LI], but our analysis suggests that during times without a large land-ice area in the northern hemisphere (e.g. before 2.82 Myr BP) the specific equilibrium climate sensitivity S[CO2,LI] was smaller than during interglacials of the Pleistocene. We thus find support for a previously proposed state-change in the climate system with the wide appearance of northern hemispheric ice sheets. This study points for the first time to a so far overlooked non-linearity in the land-ice albedo radiative forcing, which is important for similar paleo data-based approaches to calculate climate sensitivity. However, the implications of this study for a suggested warming under CO2 doubling are not yet entirely clear since the necessary corrections for other slow feedbacks are in detail unknown and the still existing uncertainties in the ice sheet simulations and global temperature reconstructions are large.