Short antimicrobial host-defense peptides represent a possible alternative as lead structures to fight antibiotic resistant bacterial infections. Bac2A is a 12-mer linear variant of the naturally occurring bovine host defense peptide, bactenecin, and demonstrates moderate, broad-spectrum antimicrobial activity against Gram-positive and Gram-negative bacteria as well as against the yeast Candida albicans. With the assistance of a method involving peptide synthesis on a cellulose support, the primary sequence requirements for antimicrobial activity against the human pathogen Pseudomonas aeruginosa of 277 Bac2A variants were investigated by using a luciferase-based assay. Sequence scrambling of Bac2A led to activities ranging from superior or equivalent to Bac2A to inactive, indicating that good activity was not solely dependent on the composition of amino acids or the overall charge or hydrophobicity, but rather required particular linear sequence patterns. A QSAR computational analysis was applied to analyze the data resulting in a model that supported this sequence pattern hypothesis. The activity of selected peptides was confirmed by conventional minimal inhibitory concentration (MIC) analyses with a panel of human pathogen bacteria and fungi. Circular-dichroism (CD) spectroscopy with selected peptides in liposomes and membrane depolarization assays were consistent with a relationship between structure and activity. An additional optimization process was performed involving systematic amino acid substitutions of one of the optimal scrambled peptide variants, resulting in superior active peptide variants. This process provides a cost and time effective enrichment of new candidates for drug development, increasing the chances of finding pharmacologically relevant peptides.