Background & motivation: Peptides and proteins can interact with heme through His, Tyr, or Cys in heme-regulatory motifs (HRMs). The Cys-Pro dipeptide is a well investigated HRM, but for His and Tyr such a distinct motif is currently unknown. In addition, many heme-peptide complexes, such as heme-amyloid β, can display a peroxidase-like activity, albeit there is little understanding of how the local primary and secondary coordination environment influences catalytic activity. We thus systematically evaluated a series of His- and Tyr-based peptides to identify sequence features for high-affinity heme binding and their impact on the catalytic activity of heme. Methods: We employed solid-phase peptide synthesis to produce 58 nonapeptides, which were investigated by UV/vis, resonance Raman, and 2D NMR spectroscopy. A chromogenic assay was used to determine the catalytic activity of the heme-peptide complexes. Results: Heme-binding affinity and binding mode were found to be dependent on the coordinating amino acid and spacer length between multiple potential coordination sites in a motif. In particular, HXH and HXXXH motifs showed strong heme binding. Analysis of the peroxidase-like activity revealed that some of these peptides and also HXXXY motifs enhance the catalytic activity of heme significantly. Conclusions: We identify HXH, HXXXH, and HXXXY as potential new HRMs with functional properties. Several peptides displayed a strikingly high peroxidase-like activity. General significance: The identification of HRMs allows to discover yet unknown heme-regulated proteins, and consequently, enhances our current understanding of pathologies involving labile heme.