Studying cancer metabolism gives insight into tumorigenic survival mechanisms and susceptibilities. In melanoma, we identify HEXIM1, a transcription elongation regulator, as a melanoma tumor suppressor that responds to nucleotide stress. HEXIM1 expression is low in melanoma. Its overexpression in a zebrafish melanoma model suppresses cancer formation, while its inactivation accelerates tumor onset in vivo. Knockdown of HEXIM1 rescues zebrafish neural crest defects and human melanoma proliferation defects that arise from nucleotide depletion. Under nucleotide stress, HEXIM1 is induced to form an inhibitory complex with P-TEFb, the kinase that initiates transcription elongation, to inhibit elongation at tumorigenic genes. The resulting alteration in gene expression also causes anti-tumorigenic RNAs to bind to and be stabilized by HEXIM1. HEXIM1 plays an important role in inhibiting cancer cell-specific gene transcription while also facilitating anti-cancer gene expression. Our study reveals an important role for HEXIM1 in coupling nucleotide metabolism with transcriptional regulation in melanoma.