Molecular noise in bacterial restriction-modification systems can cause rare events of host DNA cleavage at restriction sites. Such noise-induced selective pressure may result in evolved sequences exhibiting restriction site avoidance. We identify a two-state regime of evolutionary dynamics, in which populations either develop avoidance or go extinct. Using perturbation theory, we show that equilibrium sequence statistics exhibit power-law scaling in the ratio of restriction strength to mutation rate. Noise levels comparable to mutation rates can be sufficient to evolve detectable avoidance.