Plasmids in conjunction with other mobile elements such as transposons are major players in the genetic adaptation of bacteria in response to changes in environment. Here we show that a large catabolic TOL plasmid, pWW0, from Pseudomonas putida carries genes (rulAB genes) encoding an error-prone DNA polymerase Pol V homologue which increase the survival of bacteria under conditions of accumulation of DNA damage. A study of population dynamics in stationary phase revealed that the presence of pWW0-derived rulAB genes in the bacterial genome allows the expression of a strong growth advantage in stationary phase (GASP) phenotype of P. putida. When rulAB-carrying cells from an 8-day-old culture were mixed with Pol V-negative cells from a 1-day-old culture, cells derived from the aged culture out-competed cells from the nonaged culture and overtook the whole culture. At the same time, bacteria from an aged culture lacking the rulAB genes were only partially able to out-compete cells from a fresh overnight culture of the parental P. putida strain. Thus, in addition to conferring resistance to DNA damage, the plasmid-encoded Pol V genes significantly increase the evolutionary fitness of bacteria during prolonged nutritional starvation of a P. putida population. The results of our study indicate that RecA is involved in the control of expression of the pWW0-encoded Pol V.