The E1b55K and E4orf6 proteins of adenovirus type 5 (Ad5) assemble into a complex together with cellular proteins including cullin 5, elongins B and C, and Rbx1. This complex possesses E3 ubiquitin ligase activity and targets cellular proteins for proteasome-mediated degradation. The ligase activity has been suggested to be responsible for all functions of E1b55K/E4orf6, including promoting efficient viral DNA replication, preventing a cellular DNA damage response, and stimulating late viral mRNA nuclear export and late protein synthesis. The known cellular substrates for degradation by E1b55K/E4orf6 are the Mre11/Rad50/Nbs1 DNA repair complex, the tumor suppressor p53, and DNA ligase IV. Here we show that the degradation of individual targets can occur independently of other substrates. Furthermore, we identify separation-of-function mutant forms of E1b55K that can distinguish substrates for binding and degradation. Our results identify distinct regions of E1b55K that are involved in substrate recognition but also imply that there are additional requirements beyond protein association. These mutant proteins will facilitate the determination of the relevance of specific substrates to the functions of E1b55K in promoting infection and inactivating host defenses.