The correct annotation of genes encoding the smallest proteins is one of the biggest challenges of genome annotation, and perhaps more importantly, few annotated short open reading frames have been confirmed to correspond to synthesized proteins. We used sequence conservation and ribosome binding site models to predict genes encoding small proteins, defined as having 16–50 amino acids, in the intergenic regions of the Escherichia coli genome. We tested expression of these predicted as well as previously annotated genes by integrating the sequential peptide affinity tag directly upstream of the stop codon on the chromosome and assaying for synthesis using immunoblot assays. This approach confirmed that 20 previously annotated and 18 newly discovered proteins of 16–50 amino acids are synthesized. We summarize the properties of these small proteins; remarkably more than half of the proteins are predicted to be single-transmembrane proteins, nine of which we show co-fractionate with cell membranes.