Inhibition of histone demethylases has within recent years advanced into a new strategy for treating cancer and other diseases. Targeting specific histone demethylases can be challenging as the active sites of KDM1A-B and KDM-4A-D histone demethylases, respectively, are highly conserved. Most inhibitors developed up-to-date target either the cofactor- or substrate-binding sites of these enzymes, resulting in a lack of selectivity and off-target effects. This study describes the discovery of the first peptide-based inhibitors of KDM4 histone demethylases that do not share the histone peptide sequence, or inhibit through substrate competition. Through screening of DNA-encoded peptide libraries against KDM1 and -4 histone demethylases by phage display, two cyclic peptides targeting the histone demethylase KDM4C were identified and developed as inhibitors by amino acid replacement, truncation and chemical modifications. Hydrogen/deuterium exchange mass spectrometry revealed that the peptide-based inhibitors target KDM4C through substrate-independent interactions located on the surface remote from the active site within less conserved regions of KDM4C. The sites discovered in this study provide a new approach of targeting KDM4C through substrate- and cofactor-independent interactions, and may be further explored to develop potent selective inhibitors and biological probes for the KDM4 family.