Computational structure prediction of streptavidin-peptide complexes for known recognition sequences and a number of random di-, tri-, and tetrapeptides has been conducted, and mechanisms of peptide recognition with streptavidin have been investigated by a new computational protocol. The structural consensus criterion, which is computed from multiple docking simulations and measures the accessibility of the dominant binding mode, identifies recognition motifs from a set of random peptide sequences, whereas energetic analysis is less discriminatory. The predicted conformations of recognition tripeptide and tetrapeptide sequences are also in structural harmony and composed of peptide fragments that are individually unfrustrated in their bound conformation, resulting in a minimally frustrated energy landscape for recognition peptides.