The accessory plasmid pAtC58 of the common laboratory strain of Agrobacterium tumefaciens confers numerous catabolic functions and has been proposed to play a role in virulence. Genomic sequencing of evolved laboratory strains of A. tumefaciens revealed the presence of multiple deletion events in the At plasmid, with reductions in plasmid size ranging from 25% to 30% (115-194 kb). Flanking both ends of the sites of these deletions is a short-nucleotide repeat sequence that is in a single copy in the deleted plasmids, characteristic of a phage- or transposon-mediated deletion event. This repeat sequence is widespread throughout the C58 genome, but concentrated on the At plasmid, suggesting its frequency to be nonrandom. In this study, we assess the prevalence of the larger of these deletions in multiple C58 derivatives and characterize its functional significance. We find that in addition to elevating virulence gene expression, this deletion is associated with a significantly reduced carriage cost to the cell. These observations are a clear demonstration of the dynamic nature of the bacterial genome and suggest a mechanism for genetic plasticity of these costly but otherwise stable plasmids. Additionally, this phenomenon could be the basis for some of the dramatic recombination events so ubiquitous within and among megaplasmids.