Self-organization of proteins in space and time is of crucial importance for the functioning of cellular processes. Often, this organization takes place in the presence of strong random fluctuations due to the small number of molecules involved. We report on stochastic switching of the Min-protein distributions between the two cell halves in short Escherichia coli cells. A computational model provides strong evidence that the macroscopic switching is rooted in microscopic noise on the molecular scale. In longer bacteria, the switching turns into regular oscillations that are required for positioning of the division plane. As the pattern becomes more regular, cell-to-cell variability also lessens, indicating cell length-dependent regulation of Min-protein activity.