Unicellular organisms have the prevalent challenge to survive under oxidative stress of reactive oxygen species (ROS) such as hydrogen peroxide (H2O2). ROS are present as by-products of photosynthesis and aerobic respiration. These reactive species are even employed by multicellular organisms as potent weapons against microbes. Although bacterial defences against lethal and sub-lethal oxidative stress have been studied in model bacteria, the role of fluctuating H2O2 concentrations remains unexplored. It is known that sub-lethal exposure of Escherichia coli to H2O2 results in enhanced survival upon subsequent exposure. Here we investigate the priming response to H2O2 at physiological concentrations. The basis and the duration of the response (memory) were also determined by time-lapse quantitative proteomics. We found that a low level of H2O2 induced several scavenging enzymes showing a long half-life, subsequently protecting cells from future exposure. We then asked if the phenotypic resistance against H2O2 alters the evolution of resistance against oxygen stress. Experimental evolution of H2O2 resistance revealed faster evolution and higher levels of resistance in primed cells. Several mutations were found to be associated with resistance in evolved populations affecting different loci but, counterintuitively, none of them was directly associated with scavenging systems. Our results have important implications for host colonisation and infections where microbes often encounter reactive oxygen species in gradients.