One of the most fundamental features of biological systems is probably their ability to self-organize in space and time on different scales. Despite many elaborate theoretical models of how molecular self-organization can come about, only a few experimental systems of biological origin have so far been rigorously described, due mostly to their inherent complexity. The most promising strategy of modern biophysics is thus to identify minimal biological systems showing self-organized emergent behavior. One of the best-understood examples of protein self-organization, which has recently been successfully reconstituted in vitro, is represented by the oscillations of the Min proteins in Escherichia coli. In this review, we summarize the current understanding of the mechanism of Min protein self-organization in vivo and in vitro. We discuss the potential of the Min oscillations to sense the geometry of the cell and suggest that spontaneous protein waves could be a general means of intracellular organization. We hypothesize that cooperative membrane binding and unbinding, e.g., as an energy-dependent switch, may act as an important regulatory mechanism for protein oscillations and pattern formation in the cell.