NF-kappaB, a central coordinator of immune and inflammatory responses, must be tightly regulated. We describe a NF-kappaB regulatory pathway that is driven by reversible lysine methylation of the p65 subunit, carried out by a lysine methylase, the nuclear receptor-binding SET domain-containing protein 1 (NSD1), and a lysine demethylase, F-box and leucine-rich repeat protein 11 (FBXL11). Overexpression of FBXL11 inhibits NF-kappaB activity, and a high level of NSD1 activates NF-kappaB and reverses the inhibitory effect of FBXL11, whereas reduced expression of NSD1 decreases NF-kappaB activation. The targets are K218 and K221 of p65, which are methylated in cells with activated NF-kappaB. Overexpression of FBXL11 slowed the growth of HT29 cancer cells, whereas shRNA-mediated knockdown had the opposite effect, and these phenotypes were dependent on K218/K221 methylation. In mouse embryo fibroblasts, the activation of most p65-dependent genes relied on K218/K221 methylation. Importantly, expression of the FBXL11 gene is driven by NF-kappaB, revealing a negative regulatory feedback loop. We conclude that reversible lysine methylation of NF-kappaB is an important element in the complex regulation of this key transcription factor.