Pseudomonas aeruginosa regulates the production of many exoproteins and secondary metabolites via a hierarchical quorum-sensing cascade through LasR and RhlR and their cognate signal molecules N-(3-oxododecanoyl)-L-homoserine lactone (3O-C12-HSL) and N-(butanoyl)-L-homoserine lactone (C4-HSL). In this study, we found that transcription of the quorum sensing-regulated genes lecA (coding for PA-IL lectin), lasB (coding for elastase), and rpoS appeared to be growth phase dependent and their expression could not be advanced to the logarithmic phase in cells growing in batch culture by the addition of exogenous C4-HSL and 3O-C12-HSL. To identify novel regulators responsible for this growth phase dependency, a P. aeruginosa lecA::lux reporter strain was subjected to random transposon mutagenesis. A number of mutants affected in lecA expression were found that exhibited altered production of multiple quorum sensing-dependent phenotypes. While some mutations were mapped to new loci such as clpA and mvaT and a putative efflux system, a number of mutations were also mapped to known regulators such as lasR, rhlR, and rpoS. MvaT was identified as a novel global regulator of virulence gene expression, as a mutation in mvaT resulted in enhanced lecA expression and pyocyanin production. This mutant also showed altered swarming ability and production of the LasB and LasA proteases, 3O-C12-HSL, and C4-HSL. Furthermore, addition of exogenous 3O-C12-HSL and C4-HSL to the mvaT mutant significantly advanced lecA expression, suggesting that MvaT is involved in the growth phase-dependent regulation of the lecA gene.