Gram-negative bacteria have effective methods of excluding toxic compounds, including a largely impermeable outer membrane (OM) and a range of efflux pumps. Furthermore, when cells become nutrient limited, RpoS enacts a global expression change providing cross-protection against many stresses. Here, we utilized sensitivity to an anionic detergent (sodium dodecyl sulfate [SDS]) to probe changes occurring to the cell's permeability barrier during nutrient limitation. Escherichia coli is resistant to SDS whether cells are actively growing, carbon limited, or nitrogen limited. In actively growing cells, this resistance depends on the AcrAB-TolC efflux pump; however, this pump is not necessary for protection under either carbon-limiting or nitrogen-limiting conditions, suggesting an alternative mechanism(s) of SDS resistance. In carbon-limited cells, RpoS-dependent pathways lessen the permeability of the OM, preventing the necessity for efflux. In nitrogen-limited but not carbon-limited cells, the loss of rpoS can be completely compensated for by the AcrAB-TolC efflux pump. We suggest that this difference simply reflects the fact that nitrogen-limited cells have access to a metabolizable energy (carbon) source that can efficiently power the efflux pump. Using a transposon mutant pool sequencing (Tn-Seq) approach, we identified three genes, sanA, dacA, and yhdP, that are necessary for RpoS-dependent SDS resistance in carbon-limited stationary phase. Using genetic analysis, we determined that these genes are involved in two different envelope-strengthening pathways. These genes have not previously been implicated in stationary-phase stress responses. A third novel RpoS-dependent pathway appears to strengthen the cell's permeability barrier in nitrogen-limited cells. Thus, though cells remain phenotypically SDS resistant, SDS resistance mechanisms differ significantly between growth states. IMPORTANCE: Gram-negative bacteria are intrinsically resistant to detergents and many antibiotics due to synergistic activities of a strong outer membrane (OM) permeability barrier and efflux pumps that capture and expel toxic molecules eluding the barrier. When the bacteria are depleted of an essential nutrient, a program of gene expression providing cross-protection against many stresses is induced. Whether this program alters the OM to further strengthen the barrier is unknown. Here, we identify novel pathways dependent on the master regulator of stationary phase that further strengthen the OM permeability barrier during nutrient limitation, circumventing the need for efflux pumps. Decreased permeability of nutrient-limited cells to toxic compounds has important implications for designing new antibiotics capable of targeting Gram-negative bacteria that may be in a growth-limited state.