The nucleosome acidic patch is a major interaction hub for chromatin, providing a platform for enzymes to dock and orient for nucleosome-targeted activities. To define the molecular basis of acidic patch recognition proteome wide, we performed an amino acid resolution acidic patch interactome screen. We discovered that the histone H3 lysine 36 (H3K36) demethylase KDM2A, but not its closely related paralog, KDM2B, requires the acidic patch for nucleosome binding. Despite fundamental roles in transcriptional repression in health and disease, the molecular mechanisms governing nucleosome substrate specificity of KDM2A/B, or any related JumonjiC (JmjC) domain lysine demethylase, remain unclear. We used a covalent conjugate between H3K36 and a demethylase inhibitor to solve cryogenic electron microscopy structures of KDM2A and KDM2B trapped in action on a nucleosome substrate. Our structures show that KDM2–nucleosome binding is paralog specific and facilitated by dynamic nucleosomal DNA unwrapping and histone charge shielding that mobilize the H3K36 sequence for demethylation. [Figure not available: see fulltext.].