Using a large-scale reconstruction of ancestral gene content, we show that radical changes in regulome size occur at the origins of major prokaryotic lineages. Subsequently, the duplication and deletion of regulators slows down in most lineages, except proteobacteria, significantly reducing the scaling of regulators and keeping their average proportion lineage-specific. Our results also suggest that major transitions in prokaryote evolution are related to changes in regulatory capacity rather than proteome innovations.