Herein, we report a high-throughput approach for the selection of peripheral protein domains that bind specifically to cholesterol in lipid membranes. We discovered variants of perfringolysin O, with non-conserved amino acid substitutions at regions crucial for cholesterol recognition, demonstrating an unprecedented amino acid sequence variability with binding ability for cholesterol. The developed approach provides an effective platform for a comprehensive study of protein lipid interactions.