This review considers the influence of selection pressure, fitness and population structures on the evolution of mobile genetic elements (including plasmids, phage, pathogenicity islands, transposons and insertion sequences) that constitute the horizontal gene pool of bacteria. These are considered at different scales using examples from in vitro evolutionary studies of Escherichia coli and associated bacteriophage, detailed molecular analyses of the broad host-range IncP-1 plasmids, population surveys of pseudomonad plasmids and genomic comparisons of members of the Rhizobiaceae. All biological systems show genetic redundancy (the existence of allelic variation) at some population level, i.e. within a cell, a clone, population or community. We consider the level(s) at which redundancy is expressed and how this will affect and has influenced the evolution of mobile genetic elements.