The transcription factor c-MAF could be polyubiquitinated and subsequently degraded in the proteasomes. Theoretically, any lysine residues in c-MAF could be ubiquitinated. In the present study, we tried to find out the specific lysine residue(s) mediating c-MAF ubiquitination. Through a series of mutational screens from lysine (K) to arginine (R), we found that any single lysine mutation (K to R) failed to prevent c-MAF ubiquitination, and any single lysine residue alone could not mediate c-MAF ubiquitination, which indicated that multiple lysine residues were required for c-MAF ubiquitination. Bioinformatics and computing analyses revealed that K85 and K350 could mediate c-MAF ubiquitination, which was confirmed by the cell-based assays. However, this duo was not the only pair because the K85R/K350R mutant could also be ubiquitinated. Functionally, both M12 (K85/K350) and W12 (K85R/K350R) mutants increased cyclin D2 promoter-driven luciferase activity, but they were less potent than the lysine-free counterpart (M14). In addition, M14 induced a higher level of expression of cyclin D2 at both mRNA and protein levels. Therefore, we demonstrated that c-MAF ubiquitination is mediated by multiple lysine residues, of which K85 and K350 were sufficient but not the only residues in mediating c-MAF ubiquitination. Moreover, c-MAF was found to be degraded by lysosomes. This study added a novel insight for c-MAF ubiquitination and degradation, suggesting that c-MAF stability is strictly regulated.