The use of water-soluble synthetic peptide combinatorial libraries permits the systematic examination of tens to hundreds of millions of peptides in existing microdilution assays. In the present study, we prepared and determined the antistaphylococcal activities of two new synthetic peptide combinatorial libraries (one N-acetylated, the other not) composed of tetrapeptides having one position defined and the remaining three positions made up of mixtures of L-, D-, and unnatural amino acids (a total of 58 different amino acids). These libraries, when used in conjunction with an iterative selection process, allowed for the development of a series of individually defined tetrapeptides with high levels of activity against Staphylococcus aureus. The activities of the final individual peptides against two additional strains of gram-positive bacteria (methicillin-resistant S. aureus and Streptococcus sanguis), a gram-negative bacterium (Escherichia coli), as well as the yeast Candida albicans were also determined. Cell viability assays showed that the identified peptides are bacteriostatic against both S. aureus and E. coli.