Studies of the past several decades have provided major insights into the structural organization of biological membranes and mechanisms of many membrane molecular machines. However, the origin(s) of the membrane(s) and membrane proteins remains enigmatic. We discuss different concepts of the origin and early evolution of membranes with a focus on the evolution of the (im)permeability to charged molecules such as proteins, nucleic acids and small ions. Reconstruction of the evolution of F-type and A/V-type membrane ATPases (ATP synthases), which are either proton- or sodium-dependent, might help us to understand not only the origin of membrane bioenergetics but also of membranes themselves. We argue that evolution of biological membranes occurred as a process of co-evolution of lipid bilayers, membrane proteins and membrane bioenergetics.