We have reported that JMJD5 and JMJD7 (JMJD5/7) are responsible for the clipping of arginine methylated histone tails to generate "tailless nucleosomes", which could release the pausing RNA polymerase II (Pol II) into productive transcription elongation. JMJD5/7 function as endopeptidases that cleave histone tails specifically adjacent to methylated arginine residues and continue to degrade N-terminal residues of histones via their aminopeptidase activity. Here, we report structural and biochemical studies on JMJD5/7 to understand the basis of substrate recognition and catalysis mechanism by this JmjC subfamily. Recognition between these enzymes and histone substrates is specific, which is reflected by the binding data between enzymes and substrates. High structural similarity between JMJD5 and JMJD7 is reflected by the shared common substrates and high binding affinity. However, JMJD5 does not bind to arginine methylated histone tails with additional lysine acetylation while JMJD7 does not bind to arginine methylated histone tails with additional lysine methylation. Furthermore, the complex structures of JMJD5 and arginine derivatives revealed a Tudor domain-like binding pocket to accommodate the methylated sidechain of arginine, but not lysine. There also exists a glutamine close to the catalytic center, which may suggest a unique imidic acid mediated catalytic mechanism for proteolysis by JMJD5/7.