Bacterial resistance to antibiotics has been a persistent problem in clinical and public health situations for decades. While most bacteria acquire antibiotic resistance via genes encoded in mobile genetic elements such as plasmids and transposons, many bacterial species possess an intrinsic mechanism for resistance to antibiotics, organic solvents, oxidative stressors, and household disinfectants. In the enteric bacteria Escherichia coli and other closely related bacterial species, such as pathogenic forms of E. coli and Salmonella enterica, this resistance is mediated by the activation of chromosomally encoded efflux systems, cytoplasmic reducing enzymes, and metabolic enzymes. Governing the response to these stresses are transcriptional regulatory proteins of the multiple antibiotic resistance (mar) and superoxide (sox) regulons. Although these networks respond to different environmental queues, the mar and sox systems are known to have interlocked positive and negative feedback loops that allow for coordinated, rapid response to a variety of antibiotics. In this work, we investigate how these feedback loops coordinate antibiotic resistance. Through the combined use of experimental and computational approaches, we demonstrate that the network topology of the interlocked regulons provides a robust mechanism for antibiotic resistance over a wide range of concentrations and in response to dynamic fluctuations. These results may aid in the development of new therapeutic approaches for dealing with multidrug resistance in bacterial pathogens.