Hexim1 is a cellular protein that associates with the positive transcription elongation factor b (P-TEFb) to regulate RNA polymerase II elongation of nascent mRNA transcripts. It directly binds to Cyclin T1 of P-TEFb and inhibits the kinase activity of Cdk9, leading to an arrest of transcription elongation. Here, we report the solution structure of the Cyclin T binding domain (TBD) of Hexim1 that forms a parallel coiled-coil homodimer composed of two segments and a preceding alpha helix that folds back onto the first coiled-coil unit. NMR titration, fluorescence, and immunoprecipitation experiments revealed the binding interface to Cyclin T1, which covers a large surface on the first coiled-coil segment. Electrostatic interactions between an acidic patch on Hexim1 and positively charged residues of Cyclin T1 drive the complex formation that is confirmed by mutagenesis data on Hexim1 mediated transcription regulation in cells. Thus, our studies provide structural insights how Hexim1 recognizes the Cyclin T1 subunit of P-TEFb, which is a key step toward the regulation of transcription elongation.