Heme is a crucial constituent in the organization of many living organisms. The occurrence of free organismal heme can either contribute to serious diseases or beneficially regulate important physiological processes. The regulatory function of heme on respective proteins is realized via a transient binding to small sequence stretches, i.e. heme-regulatory motifs (HRMs), located on the protein surface. Recent research achievements resulted in the discovery of a large number of Cys-based, especially Cys-Pro (CP)-based binding motifs. Although other trifunctional amino acids such as His or Tyr are also capable to coordinate the heme-iron, the number of protein representatives derived from nature is comparatively low so far. To understand transient heme association with such motifs on the molecular level, we analyzed a set of 44 His- and Tyr-based peptides using UV-vis, resonance Raman, cw-EPR and 2D NMR spectroscopy. We observed similarities with Cys-based sequences with respect to their spectral behavior and complex geometries. However, significant differences regarding heme-binding affinities and sequential requirements were also found. Compared to Cys-based peptides and proteins all sequences investigated structurally display increased flexibility already in the free state, which is also maintained upon heme association. The acquired knowledge allowed for identification and prediction of a His-based HRM in chloramphenicol acetyltransferase from E. coli as potential heme-regulated protein. The enzyme’s heme-interacting capability was studied, and revealed an inhibitory effect of heme on the protein activity with an IC50 value of 57.69 ± 4.37 μM. Thus, this finding brings microbial proteins more into focus of regulation by free heme