Human thioredoxin (hTrx), a small ubiquitous protein with strong reducing potential, has multiple biological functions, including signal transduction and regulation of the activity of transcription factors. hTrx expression is enhanced in HPV-transformed cancer cells; however, the role of hTrx in the malignant cells is not fully understood. We employed a yeast two-hybrid system to search for proteins that bind to hTrx in HeLa cells, a type of HPV-transformed human cervical cancer cell. In a screen of 1.62 × 10⁶ yeast cotransformed with a HeLa cDNA library and an hTrx vector, 13 clones were identified as candidates for hTrx-binding proteins. Among them, 3 clones were found to code in frame for the carboxyl-terminal portion of VDUP1 protein, lacking at most the first 155 residues from the start codon. A reconstructed clone carrying the full-length VDUP1 coding sequence also showed the ability to bind to an hTrx fusion protein. Loss of interaction between VDUP1 and hTrx was observed either when two cysteines (Cys 32 and 35) in hTrx were substituted by serines or when the deletion in VDUP1 was extended from amino acid position 155 to 225 or beyond. The 71-mer peptide fragment (position 155–225) of VDUP-1 alone did not bind to hTrx.