High-throughput identification of proteins and their accurate partial sequencing by shotgun nanoLC-MS/MS are now feasible for any cellular model at a full genomic scale. Proteogenomics is the integration of these data with the genome. Mining microbial proteomes allows validation of predicted orphan genes and correction of genome annotation errors such as discovery of unannotated genes, reversal of reading frames and identification of translational start sites, stop codon read-throughs or programmed frameshifts. Recent advances have been achieved in database searches, N-terminal oriented proteomics and homology-driven proteogenomics. From now on, proteogenomics on newly sequenced model genomes can be carried out at the earliest stage of the genome project as already exemplified by Mycoplasma mobile and Deinococcus deserti genomes. The proteomics and genomics alliance produces almost complete and accurate gene catalogues for small microbial genomes, a comprehensiveness which is essential for efficient systems biology.