Botulinum neurotoxin (BoNT) binds to nontoxic nonhemagglutinin (NTNHA) protein in a pH-dependent manner, and yields the protease-resistant BoNT/NTNHA complex. Here, we screened short peptides that bind to the serotype D NTNHA (NTNHA-D) using random phage display technique. NTNHA was fixed onto electrode of quartz crystal microbalance (QCM) apparatus, and then the phages displaying random heptapeptides were exposed to the NTNHA-D under the acidic condition. After rinsing with acidic buffer, the released phages under the alkaline condition were collected. The binding and release of the phage were monitored by the frequency shift on the QCM. As a result of the screening, 16 were selected as peptides that bind to NTNHA-D. The selected peptides do not share any conserved sequence, but tend to be rich in basic and/or hydrophobic amino acid. This would explain the binding manner of the BoNT to the NTNHA protein.