Lysine-specific demethylase 1A (LSD1) binds to RCOR gene family of corepressors to erase transcriptionally active marks on histones. Functional diversity in these complexes depends on the type of RCOR included, which modulates the complex´s catalytic activity. We studied the duplicative history of RCOR and LSD gene families, and analyzed the evolution of their interaction. We found that RCOR genes are the product of the two rounds of whole-genome duplications that occurred early in vertebrate evolution. In contrast, the origin of the LSD genes traces back before to the divergence of animals and plants. Coimmunoprecipitation experiments using resurrected RCOR and LSD1 proteins of the jawed vertebrate ancestor, and the common hop, date the origin of LSD1-RCOR interaction to the ancestor of animals, fungi, and plants. Overall, we trace LSD1-RCOR complex evolution and propose that animal, fungi, and plant non-model species offer advantages in addressing questions about the molecular biology of this epigenetic complex.