Phage-inducible chromosomal islands (PICIs) are a recently discovered family of pathogenicity islands that contribute substantively to horizontal gene transfer, host adaptation and virulence in Gram-positive cocci. Here we report that similar elements also occur widely in Gram-negative bacteria. As with the PICIs from Gram-positive cocci, their uniqueness is defined by a constellation of features: unique and specific attachment sites, exclusive PICI genes, a phage-dependent mechanism of induction, conserved replication origin organization, convergent mechanisms of phage interference, and specific packaging of PICI DNA into phage-like infectious particles, resulting in very high transfer frequencies. We suggest that the PICIs represent two or more distinct lineages, have spread widely throughout the bacterial world, and have diverged much more slowly than their host organisms or their prophage cousins. Overall, these findings represent the discovery of a universal class of mobile genetic elements.