The annexins are a family of Ca2+-regulated phospholipid binding proteins that are involved in membrane domain organization and membrane trafficking. Although they are widely studied and crystal structures are available for several soluble annexins their mode of membrane association has never been studied at the molecular level. Here we obtained molecular information on the annexin-membrane interaction that could serve as paradigm for the peripheral membrane association of cytosolic proteins by Molecular Dynamics simulations. We analyzed systems containing the monomeric annexin A2 (AnxA2), a membrane with negatively charged phosphatidylserine (POPS) lipids as well as Ca2+ ions. On the atomic level we identify the AnxA2 orientations and the respective residues which display the strongest interaction with Ca2+ ions and the membrane. The simulation results fully agree with earlier experimental findings concerning the positioning of bound Ca2+ ions. Furthermore, we identify for the first time a significant interaction between lysine residues of the protein and POPS lipids that occurs independently of Ca2+ suggesting that AnxA2-membrane interactions can also occur in a low Ca2+ environment. Finally, by varying Ca2+ concentrations and lipid composition in our simulations we observe a calcium-induced negative curvature of the membrane as well as an AnxA2-induced lipid ordering.