Integrons recombine gene arrays and favor the spread of antibiotic resistance. However, their broader roles in bacterial adaptation remain mysterious, partly due to lack of computational tools. We made a program – IntegronFinder – and used it to identify integrons in bacterial genomes with high accuracy and sensitivity. Some key taxa, such as α-Proteobacteria, lacked integrons suggesting they constitute deleterious genetic backgrounds for these elements. Integrons were much more frequent in intermediate size genomes, suggesting selection for compact gene acquisition. We used comparative genomics to quantify the differences between mobile and persistent integrons. The use of a covariance model to identify and align attC sites showed higher intrinsic variability in mobile integrons and a correlation between attC sites homogeneity and the number of integron cassettes. Surprisingly, numerous arrays of attC sites lacked nearby integrases (or pseudogenes of integrases), included many novel cassettes, and exhibited very diverse attC sites. These attC0 elements might provide incoming mobile integrons with a large unexplored pool of novel cassettes in genomes that currently lack integrons. They might also represent an intermediate step of the process of horizontal gene transfer following integron-capture and preceding definitive stabilization by loss of genetic mobility.