The adenovirus protein E4orf6 targets p53 for polyubiquitination and proteasomal degradation and is known to form a complex with the Cul5-ElonginB-ElonginC E3 ubiquitin ligase. However, whether Cul5 is directly responsible for the E4orf6-mediated degradation of p53 remains unclear. By using a dominant-negative mutant of Cul5 and silencing Cul5 expression through RNA interference, we have now demonstrated that E4orf6-mediated p53 degradation requires Cul5. Furthermore, we have identified a lentiviral Vif-like BC-box motif in E4orf6 that is highly conserved among adenoviruses from multiple species. More importantly, we have shown that this Vif-like BC-box is essential for the recruitment of Cul5-ElonginB-ElonginC E3 ubiquitin ligase by E4orf6 and is also required for E4orf6-mediated p53 degradation. E4orf6 selectively recruited Cul5 despite the lack of either a Cul5-box, which is used by cellular substrate receptors to recruit Cul5, or a newly identified HCCH zinc-binding motif, which is used by primate lentiviral Vif to recruit Cul5. Therefore, adenovirus E4orf6 molecules represent a novel family of viral BC-box proteins the cellular ancestor of which is as yet unknown.