Elongin is a heterotrimeric transcription elongation factor composed of subunits A, B, and C in mammals. Elongin A and C are F-box-containing and SKP1 homologue proteins, respectively, and are therefore of interest for their potential roles in cell cycle-dependent proteolysis. Mammalian elongin C interacts with both elongin A and elongin B, as well as with the von Hippel-Lindau tumor suppressor protein VHL. To investigate the corresponding interactions in yeast, we have utilized NMR spectroscopy combined with ultracentrifugal sedimentation experiments to examine complexes of yeast elongin C (Elc1) with yeast elongin A (Ela1) and two peptides from homologous regions of Ela1 and human VHL. Elc1 alone is a homotetramer composed of subunits with a structured N-terminal region and a dynamically unstable C-terminal region. Binding of a peptide fragment of the Elc1-interaction domain of Ela1 or with a homologous peptide from VHL promotes folding of the C-terminal region of Elc1 into two regular helical structures and dissociates Elc1 into homodimers. Moreover, analysis of the complex of Elc1 with the full Elc1-interaction domain of Ela1 reveals that the Elc1 homodimer is dissociated to preferentially form an Ela1/Elc1 heterodimer. Thus, elongin C is found to oligomerize in solution and to undergo significant structural rearrangements upon binding of two different partner proteins. These results suggest a structural basis for the interaction of an F-box-containing protein with a SKP1 homologue and the modulation of this interaction by the tumor suppressor VHL.