Fluoroquinolone resistance in Pseudomonas aeruginosa is mainly attributable to the constitutive expression of the xenobiotic efflux pump and mutation in DNA gyrase or topoisomerase IV. We constructed cells with a double-mutation in gyrA and mexR encoding DNA gyrase and repressor for the mexAB-oprM operon, respectively. The mutant showed 1,024 times higher fluoroquinolone resistance than cells lacking the MexAB-OprM. Cells with a single mutation in gyrA and producing a wild-type level of the MexAB-OprM efflux pump showed 128 times higher fluoroquinolone resistance than cells lacking the MexAB-OprM. In contrast, a single mutation in gyrA or mexR caused only 4 and 64 times higher resistance, respectively. These findings manifested the interplay between the MexAB-OprM efflux pump and the target mutation in fluoroquinolone resistance.