Perfringolysin O (PFO) is the prototype for the cholesterol-dependent cytolysins, a family of bacterial pore-forming toxins that act on eukaryotic membranes. The pore-forming mechanism of PFO exhibits an absolute requirement for membrane cholesterol, but the complex interplay between the structural arrangement of the PFO C-terminal domain and the distribution of cholesterol in the target membrane is poorly understood. Herein we show that PFO binding to the bilayer and the initiation of the sequence of events that culminate in the formation of a transmembrane pore depend on the availability of free cholesterol at the membrane surface, while changes in the acyl chain packing of the phospholipids and cholesterol in the membrane core, or the presence or absence of detergent-resistant domains do not correlate with PFO binding. Moreover, PFO association with the membrane was inhibited by the addition of sphingomyelin, a typical component of membrane rafts in cell membranes. Finally, addition of molecules that do not interact with PFO, but intercalate into the membrane and displace cholesterol from its association with phospholipids (e.g., epicholesterol), reduced the amount of cholesterol required to trigger PFO binding. Taken together, our studies reveal that PFO binding to membranes is triggered when the concentration of cholesterol exceeds the association capacity of the phospholipids, and this cholesterol excess is then free to associate with the toxin.