Transcription complexes that assemble at the HIV-1 promoter efficiently initiate transcription but generate paused RNA polymerase II downstream from the start site. The virally encoded Tat protein hijacks positive transcription elongation factor b (P-TEFb) to phosphorylate and activate this paused polymerase. In addition, Tat undergoes a series of reversible post-translational modifications that regulate distinct steps of the transcription cycle. To identify additional functionally important Tat cofactors, we performed RNAi knockdowns of sixteen previously identified Tat interactors and found that a novel E3 ligase, PJA2, ubiquitinates Tat in a non-degradative manner and specifically regulates the step of HIV transcription elongation. Interestingly, several different lysine residues in Tat can function as ubiquitin acceptor sites, and variable combinations of these lysines support both full transcriptional activity and viral replication. Further, the polyubiquitin chain conjugated to Tat by PJA2 can itself be assembled through variable ubiquitin lysine linkages. Importantly, proper ubiquitin chain assembly by PJA2 requires that Tat first binds its P-TEFb cofactor. These results highlight that both the Tat substrate and ubiquitin modification have plastic site usage, and this plasticity is likely another way in which the virus exploits the host molecular machinery to expand its limited genetic repertoire.