The existence of overlapping genes (OLGs) with significant coding overlaps revolutionises our understanding of genomic complexity. We report two exceptionally long (957 nt and 1536 nt), evolutionarily novel, translated antisense open reading frames (ORFs) embedded within annotated genes in Pseudomonas aeruginosa. Both OLG pairs show features consistent with being genes and transcriptional signals as indicated by transcriptome sequencing. Translation of both OLGs was confirmed by ribosome profiling as well as mass spectrometry. Quantitative proteomics of samples taken during different phases of growth revealed regulation of protein abundances, implying biological functionality. Both OLGs are taxonomically highly restricted and likely arose by overprinting within the genus. Evidence for purifying selection further supports functionality. The here established OLGs are the longest yet proposed in prokaryotes and are the best attested in terms of translation and evolutionary constraint.