Chromatin-modifying enzymes target distinct residues within histones to finetune gene expression profiles. SIRT7 is an NAD-dependent deacylase often deregulated in cancer, which deacetylates either H3 lysine 36 (H3K36) or H3K18 with high specificity within nucleosomes. Here, we report structures of nucleosome-bound SIRT7, and uncover the structural basis of its specificity towards H3K36 and K18 deacylation, combining a mechanism-based cross-linking strategy, cryo-EM, and enzymatic and cellular assays. We show that the SIRT7 N-terminus represents a unique, extended nucleosome-binding domain, reaching across the nucleosomal surface to the acidic patch. The catalytic domain binds at the H3-tail exit site, engaging both DNA gyres of the nucleosome. Contacting H3K36 versus H3K18 requires a change in binding pose, and results in structural changes in both SIRT7 and the nucleosome. These structures reveal the basis of lysine specificity, allowing us to engineer SIRT7 towards enhanced H3K18ac selectivity, and provides a basis for small molecule modulator development.