Prevention and correction of oxidative DNA lesions in Pseudomonas aeruginosa is ensured by the DNA oxidative repair system (GO). Single inactivation of mutT, mutY and mutM involved in GO led to elevated mutation rates (MRs) that correlated to increased development of resistance to antibiotics. In this study, we constructed a double mutant in mutY and mutM (PAOMY-Mgm) and characterized the phenotype and the gene expression profile using microarray and RT-PCR. PAOMY-Mgm presented 28-fold increases in MR compared with wild-type reference strain PAO1. In comparison, the PAOMYgm (mutY) single mutant showed only a fivefold increase, whereas the single mutant PAOMMgm (mutM) showed a nonsignificant increase in MR compared with PAO1 and the single mutants. Mutations in the regulator nfxB leading to hyperexpression of MexCD-OprJ efflux pump were found as the mechanism of resistance to ciprofloxacin in the double mutant. A better fitness of the mutator compared with PAO1 was found in growth competition experiments in the presence of ciprofloxacin at concentrations just below minimal inhibitory concentration. Up-regulation of the antimutator gene pfpI, that has been shown to provide protection to oxidative stress, was found in PAOMYMgm compared with PAO1. In conclusion, we showed that MutY and MutM are cooperating in the GO of P. aeruginosa, and that oxidative DNA lesions might represent an oxidative stress for the bacteria.