Recoverin is a neuronal calcium sensor involved in vision adaptation that reversibly associates with cellular membranes via its calcium-activated myristoyl switch. While experimental evidence shows that the myristoyl group significantly enhances membrane affinity of this protein, molecular details of the binding process are still under debate. Here, we present results of extensive molecular dynamics simulations of recoverin in the proximity of a phospholipid bilayer. We capture multiple events of spontaneous membrane insertion of the myristoyl moiety and confirm its critical role in the membrane binding. Moreover, we observe that the binding strongly depends on the conformation of the N-terminal domain. We propose that a suitable conformation of the N-terminal domain can be stabilized by the disordered C-terminal segment or by binding of the target enzyme, i.e., rhodopsin kinase. Finally, we find that the presence of negatively charged lipids in the bilayer stabilizes a physiologically functional orientation of the membrane-bound recoverin.