Molecules capable of mimicking protein binding and/or functional sites present useful tools for a range of biomedical applications, including the inhibition of protein-ligand interactions. Such mimics of protein binding sites can currently be generated through structure-based design and chemical synthesis. Computational protein design could be further used to optimize protein binding site mimetics through rationally designed mutations that improve intermolecular interactions or peptide stability. Here, as a model for the study, we chose an interaction between human acetylcholinesterase (hAChE) and its inhibitor fasciculin-2 (Fas) because the structure and function of this complex is well understood. Structure-based design of mimics of the hAChE binding site for Fas yielded a peptide that binds to Fas at micromolar concentrations. Replacement of hAChE residues known to be essential for its interaction with Fas with alanine, in this peptide, resulted in almost complete loss of binding to Fas. Computational optimization of the hAChE mimetic peptide yielded a variant with slightly improved affinity to Fas, indicating that more rounds of computational optimization will be required to obtain peptide variants with greatly improved affinity for Fas. CD spectra in the absence and presence of Fas point to conformational changes in the peptide upon binding to Fas. Furthermore, binding of the optimized hAChE mimetic peptide to Fas could be inhibited by hAChE, providing evidence for a hAChE-specific peptide-Fas interaction.