Bacteria transcribe adjacent genes as operons, producing single polycistronic transcripts carrying multiple protein-coding genes. The common paradigm of the operon dictates that the mRNA of genes belonging to the same polycistronic unit will be present in equal stoichiometry. In contrast to this paradigm, we find that in nearly 20% of all E. coli operons, genes display alternative stoichiometries despite being coded from the same operon. Using high-throughput RNA termini mapping we find that these altered operon stoichiometries are shaped post transcriptionally by differential mRNA decay, which is regulated by RNA structures that protect specific regions in the transcript from degradation. These protective RNA structures are coded within the protein-coding regions of genes and are highly conserved between bacteria. In accordance, we find that operons that are stoichiometry-altered in E. coli are also similarly altered in other, sometimes phylogenetically distant bacteria, suggesting that operon reshaping by differential decay is a major and widespread form of regulation in bacteria. Finally, we describe a set of highly conserved ncRNAs in bacteria, so far overlooked, that are generated via a complex network of protective RNA elements and controlled degradation. Our results highlight differential mRNA decay as a major shaping force of bacterial transcriptomes.