In vitro selection targeting an anti-polyhistidine monoclonal antibody was performed using mRNA display with a random, unconstrained 27-mer peptide library. After six rounds of selection, epitope-like peptides were identified that contain two to five consecutive, internal histidines and are biased for arginine residues, without any other identifiable consensus. The epitope was further refined by constructing a high-complexity, unidirectional fragment library from the final selection pool. Selection by mRNA display minimized the dominant peptide from the original selection to a 15-residue functional sequence (peptide Cmin: RHDAGDHHHHHGVRQ; K(D) = 38 nM). Other peptides recovered from the fragment library selection revealed a separate consensus motif (ARRXA) C-terminal to the histidine track. Kinetics measurements made by surface plasmon resonance, using purified Fab (antigen-binding fragment) to prevent avidity effects, demonstrate that the selected peptides bind with 10- to 75-fold higher affinities than a hexahistidine peptide. The highest affinity peptides (K(D) approximately 10 nM) encode both a short histidine track and the ARRXA motif, suggesting that the motif and other flanking residues make important contacts adjacent to the core polyhistidine-binding site and can contribute >2.5 kcal/mol of binding free energy. The fragment library construction methodology described here is applicable to the development of high-complexity protein or cDNA expression libraries for the identification of protein-protein interaction domains.