Nuclear factor-kappa B (NF-kappa B)/Rel transcription factors are key regulators of a variety of genes involved in inflammatory responses, growth, differentiation, apoptosis, and development. There are increasing lines of evidence that NF-kappa B/Rel activity is controlled to a great extent by its phosphorylation state. In this study, we demonstrated that RelA physically associated with protein phosphatase 2A (PP2A) subunit A (PR65). Both the N- and C-terminal regions of RelA were responsible for the PP2A binding. RelA co-immunoprecipitated with PP2A in melanocytes in the absence of stimulation, indicating that RelA forms a signaling complex with PP2A in the cells. RelA was dephosphorylated by a purified PP2A core enzyme, a heterodimer formed by the catalytic subunit of PP2A (PP2Ac) and PR65, in a concentration-dependent manner. Okadaic acid, an inhibitor of PP2A at lower concentration, increased the basal phosphorylation of RelA in melanocytes and blocked the dephosphorylation of RelA after interleukin-1 stimulation. Interestingly, PP2A immunoprecipitated from melanocytes was able to dephosphorylate RelA, whereas PP2A immunoprecipitated from melanoma cell lines exhibited decreased capacity to dephosphorylate RelA in vitro. Moreover, in melanoma cells in which I kappa B kinase activity was inhibited by sulindac to a similar level as in melanocytes, the phosphorylation state of RelA and the relative NF-kappa B activity were still higher than those in normal melanocytes. These data suggest that the constitutive activation of RelA in melanoma cells (Yang, J., and Richmond, A. (2001) Cancer Res. 61, 4901-4909) could be due, at least in part, to the deficiency of PP2A, which exhibits decreased dephosphorylation of NF-kappa B/RelA.