Amyloid fibrils and peptide oligomers play central roles in the pathology of Alzheimer's disease, type 2 diabetes, Parkinson's disease, Huntington's disease, and prion-related disease. Here, we investigate the molecular interactions between preformed amyloid β (Aβ) molecular protofilaments and lipid bilayer membranes, in the presence of explicit water molecules, using computational models and all-atom molecular dynamics. These interactions play an important role in the stability and function of both Aβ fibrils and the adjacent cellular membrane. Taking advantage of the symmetry-related and directional properties of the protofilaments, we build models that cover several relative protofilament-membrane orientations. Our molecular dynamics simulations reveal the relative contributions of different structural elements to the dynamics and stability of Aβ protofilament segments near membranes, and the first steps in the mechanism of fibril-membrane interactions. During this process, we observe a significant alteration of the side-chain contact pattern in protofilaments, although a fraction of the characteristic β-sheet content is preserved. As a major driving force, we identify the electrostatic interactions between Aβ charged side chains, including E22, D23, and K28, and lipid headgroups. Together with hydrogen bonding with atoms from lipid headgroups, these interactions can facilitate the penetration of hydrophobic C-terminal amino acids through the lipid headgroup region, which can finally lead both to further loss of the initial fibril structure and to local membrane-thinning effects. Our results may guide new experiments that could test the extent to which the structural features of water-formed amyloid fibrils are preserved, lost, or reshaped by membrane-mediated interactions.