The depletion of cholesterol from membranes, mediated by β-cyclodextrin (β-CD) is well known and documented, but the molecular details of this process are largely unknown. Using molecular dynamics simulations, we have been able to study the CD mediated extraction of cholesterol from model membranes, in particular from a pure cholesterol monolayer, at atomic resolution. Our results show that efficient cholesterol extraction depends on the structural distribution of the CDs on the surface of the monolayer. With a suitably oriented dimer, cholesterol is extracted spontaneously on a nanosecond time scale. Additional free energy calculations reveal that the CDs have a strong affinity to bind to the membrane surface, and, by doing so, destabilize the local packing of cholesterol molecules making their extraction favorable. Our results have implications for the interpretation of experimental measurements, and may help in the rational design of efficient CD based nano-carriers.