There is an urgent need to coat the surfaces of medical devices, including implants, with antimicrobial agents to reduce the risk of infection. A peptide array technology was modified to permit the screening of short peptides for antimicrobial activity while tethered to a surface. Cellulose-amino-hydroxypropyl ether (CAPE) linker chemistry was used to synthesize, on a cellulose support, peptides that remained covalently bound during biological assays. Among 122 tested sequences, the best surface-tethered 9-, 12-, and 13-mer peptides were found to be highly antimicrobial against bacteria and fungi, as confirmed using alternative surface materials and coupling strategies as well as coupling through the C and N termini of the peptides. Structure-activity modeling of the structural features determining the activity of tethered peptides indicated that the extent and positioning of positive charges and hydrophobic residues were influential in determining activity.