More than 80 small, regulatory RNAs (sRNAs) and 60 proteins of 16-50 amino acids (small proteins) are encoded in the E. coli genome. The vast majority of the corresponding genes have no known function. We screened 125 DNA bar-coded mutants to identify novel cell envelope stress and acute acid shock phenotypes associated with deletions of genes coding for sRNAs and small proteins. Nine deletion mutants (ssrA, micA, ybaM, ryeF, yqcG, sroH, ybhT, yobF, and glmY) are sensitive to cell envelope stress and two are resistant (rybB and blr). Deletion mutants of genes coding for four small proteins (yqgB, mgrB, yobF, and yceO) are sensitive to acute acid stress. We confirmed each of these phenotypes in one-on-one competition assays against otherwise wild-type lacZ mutant cells. A more detailed investigation of the SsrA phenotype suggests that ribosome release is critical for resistance to cell envelope stress. The bar-coded deletion collection we generated can be screened for sensitivity or resistance to virtually any stress condition.