Heme plays versatile and fascinating roles in controlling fundamental biological processes. Heme serves as a signaling molecule for oxygen levels in yeast, as heme function is entwined to molecular oxygen. Heme and oxygen regulate the expression of many genes in eukaryotes by modulating activity of regulatory proteins. In yeast, Gis1 is a DNA-binding transcriptional regulator belonging to the JHDM3/JMJD2 subfamily of demethylases. It is highly homologous to the mammalian JmjC domain containing protein JMJD2b, which plays an important role in histone demethylation, oxygen regulation and hormonal signaling. This study aims to dissect the molecular interactions regulating Gis1 activity by determining the effect of heme, oxygen and Gis1 interacting proteins on regulation of transcriptional activity and demethylase activity of Gis1. Notably, recent experiments in our lab showed that Gis1 senses changes in oxygen and heme levels, and its transcriptional activity is controlled stringently by heme concentration. Gis1 is a unique transcriptional regulator containing 894 amino acid residues with multiple domains and complex biological functions. Our biochemical studies indicate that heme binds directly to Gis1 and JMJD2b proteins. We also identified via mass spectrometric analysis that Gis1 interacts with different set of proteins under conditions of hypoxia, low heme and high heme. Together, our results show that Gis1 represents a novel class of complex transcriptional regulators mediating heme signaling.