While the oxygen-dependent reversal of lysine Nɛ-methylation is well established, the existence of bona fide Nω-methylarginine demethylases (RDMs) is controversial. Lysine demethylation, as catalysed by two families of lysine demethylases (the flavin-dependent KDM1 enzymes and the 2-oxoglutarate- and oxygen-dependent JmjC KDMs, respectively), proceeds via oxidation of the N-methyl group, resulting in the release of formaldehyde. Here we report detailed biochemical studies clearly demonstrating that, in purified form, a subset of JmjC KDMs can also act as RDMs, both on histone and non-histone fragments, resulting in formaldehyde release. RDM catalysis is studied using peptides of wild-type sequences known to be arginine-methylated and sequences in which the KDM’s methylated target lysine is substituted for a methylated arginine. Notably, the preferred sequence requirements for KDM and RDM activity vary even with the same JmjC enzymes. The demonstration of RDM activity by isolated JmjC enzymes will stimulate efforts to detect biologically relevant RDM activity.