Cholesterol-Dependent Cytolysins (CDC’s) are bacterial pore-forming toxins that form large oligomeric pores in lipid bilayers. Intermedilysin (ILY) is an archetypal member of a subclass of CDC’s that requires the presence of the complement inhibitor CD59 in addition to cholesterol for pore formation. Here we present an interdisciplinary structural and biochemical approach to understanding the temporal role of cholesterol and CD59 in binding, oligomerisation and membrane penetration of ILY. The crystal structure of ILY in complex with CD59 reveals a dual binding site, indicating a role of CD59 in the specific co-ordination of ILY monomers nucleating an early prepore state. Using model membrane systems we have further clarified the roles of CD59 and cholesterol. Liposomes and lipid monolayers with and without cholesterol were generated containing soluble CD59, modified to possess a myristoylated lysine-rich“cytotopic” peptide. Using a combination of non-denaturing AGE gels, electron microscopy, and fluorescence-based lysis assays we probed the system for membrane association, oligomeric ILY rings, and membrane penetration, respectively. Our results suggest that ILY’s interaction with cholesterol is the first point of contact with the lipid membrane, tethering the toxin to the bilayer. CD59 is less important for membrane targeting, but is essential in the assembly of productive ILY oligomers. However, these rings are lysis incompetent without cholesterol, and can disassociate from the membrane as soluble oligomers. This suggests that CD59 releases ILY upon oligomerization but before membrane penetration. Association with cholesterol is therefore essential for further membrane anchoring post-CD59 dissociation either by direct interaction with the lipid itself and or the necessity for the lipid in triggering further protein conformational changes that lead to membrane penetration.