Recent evidence has revealed that senescence induction requires fine-tuned activation of p53, however, mechanisms underlying the regulation of p53 activity during senescence have not as yet been clearly established. We demonstrate here that SCF^Fbxo22-KDM4A is a senescence-associated E3 ligase targeting methylated p53 for degradation. We find that Fbxo22 is highly expressed in senescent cells in a p53-dependent manner, and that SCF^Fbxo22 ubiquitylated p53 and formed a complex with a lysine demethylase, KDM4A. Ectopic expression of a catalytic mutant of KDM4A stabilizes p53 and enhances p53 interaction with PHF20 in the presence of Fbxo22. SCF^Fbxo22-KDM4A is required for the induction of p16 and senescence-associated secretory phenotypes during the late phase of senescence. Fbxo22^−/− mice are almost half the size of Fbxo22^+/− mice owing to the accumulation of p53. These results indicate that SCF^Fbxo22-KDM4A is an E3 ubiquitin ligase that targets methylated p53 and regulates key senescent processes.