In this work we addressed the role of ubiquitination in the function of the nascent polypeptide-associated complex (NAC), named EGD in the yeast Saccharomyces cerevisiae. To this end, we first identified the lysines residues required for ubiquitination of EGD/NAC. While simultaneous mutation of many lysines in the alpha-subunit of NAC (Egd2p) was required to abolish its ubiquitination, for the beta-subunit of NAC (Egd1p), mutation of K29 and K30 was sufficient. We determined that the ubiquitination of the two EGD subunits was coordinated, occurring during growth first on Egd1p and then on Egd2p. Egd2p was ubiquitinated earlier during growth if Egd1p could not be ubiquitinated. The use of mutants revealed the importance of EGD ubiqutination for its ribosome association and stability. Finally, our study demonstrated an interaction of EGD/NAC with the proteasome and revealed the importance of the Not4p E3 ligase, responsible for EGD/NAC ubiquitination, in this association.