Calmodulin (CaM) is a ubiquitous calcium-sensitive messenger in eukaryotic cells. It was previously shown that CaM possesses an affinity for diverse lipid moieties, including those found on CaM-binding proteins. These facts, together with our observation that CaM accumulates in membrane-rich protrusions of HeLa cells upon increased cytosolic calcium, motivated us to perform a systematic search for unmediated CaM interactions with model lipid membranes mimicking the cytosolic leaflet of plasma membranes. A range of experimental techniques and molecular dynamics simulations prove unambiguously that CaM interacts with lipid bilayers in the presence of calcium ions. The lipids phosphatidylserine (PS) and phosphatidylethanolamine (PE) hold the key to CaM–membrane interactions. Calcium induces an essential conformational rearrangement of CaM, but calcium binding to the headgroup of PS also neutralizes the membrane negative surface charge. More intriguingly, PE plays a dual role—it not only forms hydrogen bonds with CaM, but also destabilizes the lipid bilayer increasing the exposure of hydrophobic acyl chains to the interacting proteins. Our findings suggest that upon increased intracellular calcium concentration, CaM and the cytosolic leaflet of cellular membranes can be functionally connected.