While current peptide optimization uses a relatively small number of canonical and commercially available non-natural amino acids, the chemical spaces available for small molecule drug discovery are in the billions of molecules. In the present study, we describe the development of a large virtual library of readily synthesizable non-natural amino acids that can power the virtual screening protocols and aid in peptide optimization. To that end, we enumerated nearly 380 thousand amino acids and demonstrated their vast chemical diversity compared to the 20 canonical and commercial residues. Furthermore, we selected a 10 thousand amino acid subset to validate our virtual screening workflow on the Keap1–Neh2 complex model system. Through in silico mutations of Neh2 peptide residues to those from the virtual library, our docking-based protocol identified a number of possible solutions with a significantly higher predicted affinity towards the Keap1 protein. This protocol demonstrates that the non-natural amino acid chemical space can be massively extended and virtually screened with a reasonable computational cost.