Protein kinase CK2 is a ubiquitous and pleiotropic Ser/Thr protein kinase involved in cell growth and transformation. Here we report the identification by yeast interaction trap of a CK2 interacting protein, UBC3B, which is highly homologous to the E2 ubiquitin conjugating enzyme UBC3/CDC34. UBC3B complements the yeast cdc34-2 cell cycle arrest mutant in S. cerevisiae and transfers ubiquitin to a target substrate in vitro. UBC3B is specifically phosphorylated by CK2 in vitro and in vivo. We mapped by deletions and site directed mutagenesis the phosphorylation site to a serine residue within the C-terminal domain in position 233 of UBC3B and in the corresponding serine residue of UBC3. Following CK2-dependent phosphorylation both UBC3B and UBC3 bind to the F-box protein beta-TrCP, the substrate recognition subunit of an SCF (Skp1, Cul1, F-box) ubiquitin ligase. Furthermore, we observed that co-transfection of CK2alpha' together with UBC3B, but not with UBC3DeltaC, enhances the degradation of beta-catenin. Taken together these data suggest that CK2-dependent phosphorylation of UBC3 and UBC3B functions by regulating beta-TrCP substrate recognition.