E-selectin is a cell-adhesion receptor with specific recognition capacity toward sialo-fucosylated Lewis carbohydrates present in leukocytes and tumor cells. E-selectin interactions mediate the progress of inflammatory processes and tumor metastasis, which aroused the interest in using this protein as a biomolecular target to design glycomimetic inhibitors for active targeting or therapeutic purposes. In this work, we report the rational discovery of two novel glycomimetic peptides targeting E-selectin based on mutations of the reference selectin-binding peptide IELLQAR. Sixteen single or double mutants at Ile1, Leu3, Leu4, and Arg7 residues were evaluated as potential candidates for E-selectin targeting using 50 ns molecular dynamics (MD) simulations. Nine peptides showing a stable association with the functional pocket were modified by adding a cysteine residue to the N-terminus to confer versatility for further chemical conjugation. Subsequent 50 ns MD simulations resulted in five cysteine-modified peptides with retained or improved E-selectin binding potential. Then, 300 ns accelerated MD (aMD) simulations were used to examine the binding properties of the best five cysteine-modified peptides. CIEELQAR and CIELFQAR exhibit the most selective association with the functional pocket of E-selectin, as revealed by potential of mean force profiles. Microscale thermophoresis experiments confirmed the E-selectin binding capacity of the selected peptides with KD values in the low micromolar range (CIEELQAR KD = 35.0 ± 1.4 μM; CIELFQAR KD = 16.4 ± 0.7 μM), which are 25-fold lower than the reported value for the native ligand sLex (KD = 878 μM). Our findings support the potential of CIEELQAR and CIELFQAR as novel E-selectin-targeting peptides with high recognition capacity and versatility for chemical conjugation, which are critical for enabling future applications in active targeting.