A positive feedback loop is a common network motif in genetic regulatory networks often associated with developmental cell-fate decisions, memory, and bistable “all-or-none” responses. An often-stated “necessary” condition for bistability predicted by deterministic dynamic models is the presence of non-linear, switch-like feedback. A common molecular mechanism given to account for the non-linear response is cooperative binding of transcription factors to multiple binding sites within the promoter of a gene. Surprisingly, we find experimentally that linear feedback is capable of generating bistable gene expression with highly separated “ON” and “OFF” states. Furthermore, the bistable expression occurs only when multiple binding sites are present. In agreement with theoretical models, we show that noise in gene expression is responsible for the bistability. Using both single cell protein and mRNA measurements, we show that multiple binding sites lead to bistable gene expression by severely increasing this noise. We also propose a mechanism and model for how multiple binding sites increase gene expression noise. To our knowledge, this is the first experimental demonstration of noise-induced bistability in gene expression. Furthermore, it opens up questions as to what extent robust “all-or-none” responses are observed in settings where there is not significant evidence of non-linear feedback.