The recognition and binding of cholesterol is an important feature of many eukaryotic, viral, and prokaryotic proteins, but the molecular details of such interactions are understood only for a few proteins. The pore-forming cholesterol-dependent cytolysins (CDCs) contribute to the pathogenic mechanisms of a large number of Gram-positive bacteria. Cholesterol dependence of the CDC mechanism is a hallmark of these toxins, yet the identity of the CDC cholesterol recognition motif has remained elusive. A detailed analysis of membrane interactive structures at the tip of perfringolysin O (PFO) domain 4 reveals that a threonine-leucine pair mediates CDC recognition of and binding to membrane cholesterol. This motif is conserved in all known CDCs and conservative changes in its sequence or order are not well tolerated. Thus, the Thr-Leu pair constitutes a common structural basis for mediating CDC-cholesterol recognition and binding, and defines a unique paradigm for membrane cholesterol recognition by surface-binding proteins.