Paleoclimatic records indicate a decline of vegetation cover in the Western Sahara at the end of the African Humid Period (about 5,500 years before present). Modelling studies have shown that this phenomenon may be interpreted as a critical transition that results from a bifurcation in the atmosphere-vegetation system. However, the stability properties of this system are closely linked to climate variability and depend on the climate model and the methods of analysis. By coupling the Planet Simulator (PlaSim), an atmosphere model of intermediate complexity, with the simple dynamic vegetation model VECODE, we assess previous methods for the detection of multiple equilibria, and demonstrate their limitations. In particular, a stability diagram can yield misleading results because of spatial interactions, and the system's steady state and its dependency on initial conditions are affected by atmospheric variability and nonlinearities. In addition, we analyse the implications of climate variability for the abruptness of a vegetation decline. We find that a vegetation collapse can happen at different locations at different times. These collapses are possible despite large and uncorrelated climate variability. Because of the nonlinear relation between vegetation dynamics and precipitation the green state is initially stabilised by the high variability. When precipitation falls below a critical threshold, the desert state is stabilised as variability is then also decreased.