In a set of experiments with global atmosphere-ocean-vegetation models, we analyze the terrestrial vegetation history from the Last Glacial Maximum to the pre-industrial time. In this presentation we explore the mechanisms in the coupled atmosphere-ocean-vegetation system that initiate the migration of the African Monsoon rainfall into the Sahara and the subsequent greening of the Sahara. It is found that the vegetation-albedo-feedback is of crucial importance for the northward extension of the vegetation zone into the Sahara desert. This feedback leads to an amplified response of the African Monsoon to the orbital forcing in the early Holocene. We further discuss the changes in the terrestrial carbon storage and its implications for atmospheric CO2 concentrations. A preliminary comparison between model results and paleoproxy records is presented.