Many bacteria actively import environmental DNA and incorporate it into their genomes. This behavior, referred to as transformation, has been described in many species from diverse taxonomic backgrounds. Transformation is expected to carry some selective advantages similar to those postulated for meiotic sex in eukaryotes. However, the accumulation of loss-of-function alleles at transformation loci and an increased mutational load from recombining with DNA from dead cells create additional costs to transformation. These costs have been shown to outweigh many of the benefits of recombination under a variety of likely parameters. We investigate an additional proposed benefit of sexual recombination, the Red Queen hypothesis, as it relates to bacterial transformation. Here we describe a computational model showing that host-pathogen coevolution may provide a large selective benefit to transformation and allow transforming cells to invade an environment dominated by otherwise equal non-transformers. Furthermore, we observe that host-pathogen dynamics cause the selection pressure on transformation to vary extensively in time, explaining the tight regulation and wide variety of rates observed in naturally competent bacteria. Host-pathogen dynamics may explain the evolution and maintenance of natural competence despite its associated costs.