De novo design of peptides that bind specifically to functional proteins is beneficial for diagnostics and therapeutics. However, complex permutations and combinations of amino acids pose significant challenges to the rational design of peptides with desirable stability and affinity. Herein, we develop a computational-based evolution method, namely, peptidomimetics-driven recognition elements design (PepDRED), to derive hemoglobin-inspired peptidomimetics. PepDRED mimics the natural evolutionism pipeline to generate stable apovariant (AVs) structures for wild-type counterparts via automated point mutations and validates their efficiency through free binding energy analysis and per residue energy decomposition analysis. For application demonstration, we applied PepDRED to design de novo peptides to bind FhuA, a typical TonB-dependent transporter (TBDT). TBDTs are Gram-negative bacterial outer membrane proteins responsible for iron transport and vital for bacterial resistance. PepDRED generated a pool of AVs and proceeded to reach an optimized peptide, AV440, with a remarkable binding affinity of -21 kcal/mol. AV440 is ∼2.5-fold stronger than the existing FhuA inhibitor Microcin J25. Network energy analysis further unveils that incorporating methionine (M42) in the N-terminal region significantly enhances inter-residue contacts and binding affinity. PepDRED offers a prompt and efficient in silico approach to develop potent peptide candidates for target proteins.