The MutS, MutL, and MutH proteins play major roles in several DNA repair pathways. We previously reported that the cellular amounts of MutS and MutH decreased by as much as 10-fold in stationary-phase cultures. Consequently, we tested whether the amounts of MutS, MutL, and MutH were regulated by two global regulators, RpoS (sigma38) and Hfq (HF-I [putative RNA chaperone]), which are involved in stationary-phase transition. We report here that mutations in hfq and rpoS reversed the stationary-phase down-regulation of the amounts of MutS and MutH. hfq regulation of the amount of MutS in stationary-phase cultures was mediated by RpoS-dependent and -independent mechanisms, whereas hfq regulation of the amount of MutH was mediated only through RpoS. Consistent with this interpretation, the amount of MutS but not MutH was regulated by Hfq, but not RpoS, in exponentially growing cells. The amount of MutL remained unchanged in rpoS, hfq-1, and rpoS+, hfq+ strains in exponentially growing and stationary-phase cultures and served as a control. The beta-galactosidase activities of single-copy mutS-lacZ operon and gene fusions suggested that hfq regulates mutS posttranscriptionally in exponentially growing cultures. RNase T2 protection assays revealed increased amounts of mutS transcript that are attributed to increased mutS transcript stability in hfq-1 mutants. Lack of Hfq also increased the amounts and stabilities of transcripts initiated from P(miaA) and P1hfqHS, two of the promoters for hfq, suggesting autoregulation, but did not change the half-life of bulk mRNA. These results suggest that the amounts of MutS and MutH may be adjusted in cells subjected to different stress conditions by an RpoS-dependent mechanism. In addition, Hfq directly or indirectly regulates several genes, including mutS, hfq, and miaA, by an RpoS-independent mechanism that destabilizes transcripts.