In this work, we determine that the Saccharomyces cerevisiae Ccr4-Not complex controls ubiquitination of the conserved ribosome-associated heterodimeric EGD (enhancer of Gal4p DNA binding) complex, which consists of the Egd1p and Egd2p subunits in yeast and is named NAC (nascent polypeptide-associated complex) in mammals. We show that the EGD complex subunits are ubiquitinated proteins, whose ubiquitination status is regulated during cell growth. Egd2p has a UBA domain that is not essential for interaction with Egd1p but is required for stability of Egd2p and Egd1p. Ubiquitination of Egd1p requires Not4p. Ubiquitination of Egd2p also requires Not4p, an intact Not4p RING finger domain, and all other subunits of the Ccr4-Not complex tested. In the absence of Not4p, Egd2p mislocalizes to punctuate structures. Finally, the EGD complex can be ubiquitinated in vitro by Not4p and Ubc4p, one of the E2 enzymes with which Not4p can interact. Taken together our results reveal that the EGD ribosome-associated complex is ubiquitinated in a regulated manner, and they show a new role for the Ccr4-Not complex in this ubiquitination.