The birth of new genes from non-coding sequences has been postulated to be preceded by a proto-gene phase, in which a sequence is translated into protein but does not exhibit hallmarks of a clear function. Despite the abundance of such proto-genes in bacterial genomes, the frequency of their emergence and whether they actually act as precursors of new genes in natural populations are still open questions. To address these issues, we applied a combination of transcriptomic, proteomic and comparative genomic approaches to identify and analyze hundreds of novel bacterial protein-coding genes that have previously escaped annotation. These novel proteins, including many that are widely conserved across genera, display sequence properties indistinguishable from the non-coding regions of the genome, suggesting that the vast majority are evolving neutrally. We provide evidence of de novo emergence of three proto-genes within the history of the E. coli species; however, most such elements are formed via the mutational modification of existing open reading frames. Contrary to expectations, we discover that proto-genes emerge at a uniform rate across distant bacterial taxa despite significant differences in their genomic characteristics, suggesting the presence of taxon-specific mechanisms that regulate their origination and persistence.