Cosmogenic nuclides are typically used to either constrain an exposure age, a burial age, or an erosion rate. Constraining the landscape history and past erosion rates in previously glaciated terrains is, however, notoriously difficult because it involves a large number of unknowns. The potential use of cosmogenic nuclides in landscapes with a complex history of exposure and erosion is therefore often quite limited. Here, we present a novel multi-nuclide approach to study the landscape evolution and past erosion rates in terrains with a complex exposure history, particularly focusing on regions that were repeatedly covered by glaciers or ice sheets during the Quaternary. The approach, based on the Markov Chain Monte Carlo (MCMC) technique, focuses on mapping the range of landscape histories that are consistent with a given set of measured cosmogenic nuclide concentrations. A fundamental assumption of the model approach is that the exposure history at the site/location can be divided into two distinct regimes: i) interglacial periods characterized by zero shielding due to overlying ice and a uniform interglacial erosion rate, and ii) glacial periods characterized by 100% shielding and a uniform glacial erosion rate. We incorporate the exposure history in the model framework by applying a threshold value to the global marine benthic δ18O record and include the threshold value as a free model parameter, hereby taking into account global changes in climate. However, any available information on the glacial-interglacial history at the sampling location, in particular the timing of the last deglaciation event, is readily incorporated in the model to constrain the inverse problem. Based on the MCMC technique, the model delineates the most likely exposure history, including the glacial and interglacial erosion rates, which, in turn, makes it possible to reconstruct an exhumation history at the site. We apply the model to two landscape scenarios based on synthetic data and two landscape scenarios based on paired 10Be/26Al data from West Greenland, which makes it possible to quantify the denudation rate at these locations. The model framework, which currently incorporates any combination of the following nuclides 10Be, 26Al, 14C, and 21Ne, is highly flexible and can be adapted to many different landscape settings. The model framework may also be used in combination with physics-based landscape evolution models to predict nuclide concentrations at different locations in the landscape. This may help validate the landscape models via comparison to measured nuclide concentrations or to devise new effective sampling strategies.