Agrobacterium tumefaciens infects its plant hosts by a mechanism of horizontal gene transfer. This capability has led to its widespread use in artificial genetic transformation. In addition to DNA, the bacterium delivers an abundant ssDNA binding protein, VirE2, whose roles in the host include protection from cytoplasmic nucleases and adaptation for nuclear import. In Agrobacterium, VirE2 is bound to its acidic chaperone VirE1. When expressed in vitro in the absence of VirE1, VirE2 is prone to oligomerization and forms disordered filamentous aggregates. These filaments adopt an ordered solenoidal form in the presence of ssDNA, which was characterized previously by electron microscopy and three-dimensional image processing. VirE2 coexpressed in vitro with VirE1 forms a soluble heterodimer. VirE1 thus prevents VirE2 oligomerization and competes with its binding to ssDNA. We present here a crystal structure of VirE2 in complex with VirE1, showing that VirE2 is composed of two independent domains presenting a novel fold, joined by a flexible linker. Electrostatic interactions with VirE1 cement the two domains of VirE2 into a locked form. Comparison with the electron microscopy structure indicates that the VirE2 domains adopt different relative orientations. We suggest that the flexible linker between the domains enables VirE2 to accommodate its different binding partners.