The 'Greening' and subsequent desertification of the Sahara during the early to mid-Holocene is a dramatic example of natural climate change. We analyse a suite of simulations with a newly palaeo-conditioned configuration of the HadCM3 coupled model that is able to capture an abrupt desertification of North Africa during this time. We find that this model crosses a threshold of moisture availability for vegetation at around 6000 years before present. The resultant rapid reduction in vegetation cover acts to reduce precipitation through moisture recycling and surface albedo feedbacks. Precursor drying events which are not directly forced also indicate that the model is close to a critical moisture level. Similar precursor-like events appear in a Holocene record from the East of the continent, hinting that the natural system may resemble some of the properties of this model simulation. The overall response is not fundamentally altered by the inclusion of solar irradiance variations or volcanic eruptions. The simulated timing of the abrupt transition is mostly controlled by orbital forcing and local positive feedbacks, but it is also modulated to some extent by the state of the atmosphere and ocean. Comparisons with proxy records across North Africa show good agreement with the model simulations, although the simulations remain overly dry in the East. Overall, a threshold response may present a useful model of the real transition, but more high-resolution palaeoclimate records would help to discriminate among the predictions of climate models.