Gram-negative bacteria use type II secretion systems for the transport of virulence factors and hydrolytic enzymes through the outer membrane. These sophisticated multi-protein complexes reach from the pore in the outer membrane via the pseudopilins in the periplasm and a multi-protein inner-membrane sub-complex, to an ATPase in the cytoplasm. The human pathogen Vibrio cholerae uses such a secretion machinery, called the Eps-system, for the export of its major virulence factor cholera toxin into the intestinal tract of the human host. Here, we describe the 2.4 A structure of the hetero-tetrameric complex of the N-terminal domain of the ATPase EpsE and the cytoplasmic domain of the inner membrane protein EpsL, which constitute the major cytoplasmic components of the Eps-system. A stable fragment of EpsE in complex with the cytoplasmic domain of EpsL was identified via limited proteolysis and facilitated the crystallization of the complex. This first structure of a complex between two different proteins of the type II secretion system reveals that the N-terminal domain of EpsE and the cytoplasmic domain of EpsL form a hetero-tetramer, in which EpsL is the central dimer and EpsE binds on the periphery. The dimer of EpsL in this complex is very similar to the dimer seen in the crystal structure of the native cytoplasmic domain of EpsL, suggesting a possible physiological relevance despite a relatively small 675 A2 buried solvent accessible surface. The N-terminal domain of EpsE, which forms a compact domain with an alpha+beta-fold, places its helix alpha2 in a mostly hydrophobic cleft between domains II and III of EpsL burying 1700 A2 solvent accessible surface. This extensive interface involves several residues whose hydrophobic or charged nature is well conserved and is therefore likely to be of general importance in type II secretion systems.