Escherichia coli cytolysin A (ClyA) is an α-helical pore-forming toxin (PFT) which lyses target cells by forming membrane permeabilizing pores. The rate-determining step of this process is the conversion of the soluble ClyA monomer into a membrane inserted protomer. We elucidate the mechanism of this conformational transition using molecular dynamics simulations of coarse-grained models of ClyA and a membrane. We find that a membrane is necessary for the conformational conversion because membrane-protein interactions counteract the loss of the many intraprotein hydrophobic interactions that stabilize the membrane-inserting segments in the ClyA monomer. Of the two membrane-inserting segments, the flexible and highly hydrophobic β-tongue inserts first while the insertion of helix αA1 is membrane assisted. We conclude that the β-tongue is designed to behave as a quick-response membrane sensor, while helix αA1 improves target selectivity for cholesterol-containing cell membranes by acting as a fidelity check.