By recruiting the positive transcriptional elongation factor b (P-TEFb) to paused RNA polymerase II, the transactivator Tat stimulates transcriptional elongation of the human immunodeficiency virus type 1 (HIV-1) genome. We found that cyclin-dependent kinase 9 (Cdk9), the catalytic subunit of P-TEFb, is ubiquitylated in vivo. This ubiquitylation depended on the Skp1/Cul1/F-box protein E3 ubiquitin ligase Skp2. Likewise, Tat required Skp2 since its transactivation of the HIV-1 long terminal repeat decreased in primary mouse embryonic fibroblasts, which lacked Skp2. The ubiquitylation of Cdk9 by Skp2 facilitated the formation of the ternary complex between P-TEFb, Tat, and transactivation response element. Thus, our findings underscore the requirement of ubiquitylation for the coactivator function in regulating HIV-1 transcriptional elongation.