The bi-component leukocidins of Staphylococcus aureus are important virulence factors that lyse human phagocytic cells and contribute to immune evasion. The gamma-hemolysins (HlgAB and HlgCB) and the Panton-Valentine Leukocidin (PVL or LukSF) were shown to assemble from soluble subunits intomembrane-bound oligomers on the surface of target cells, creating barrel-like pore structures that lead to cell lysis. LukGH is the most distantly related member of this toxin family, sharing only 30-40% amino acid sequence identity with the others. We observed that, unlike the other leukocidin subunits, recombinant LukH and LukG had low solubility and were unable to bind to target cells, unless both components were present. Using biolayer interferometry and intrinsic tryptophan fluorescence we detected binding of LukH to LukG in solution with an affinity in the low nanomolar range and dynamic light scattering measurements confirmed formation of a heterodimer. We elucidated the structure of LukGH by X-ray crystallography at 2.8 Å resolution. This revealed an octameric structure which strongly resembles that reported for HlgAB, but with important structural differences. Structure guided mutagenesis studies demonstrated that three salt bridges, not found in other bi-component leukocidins, are essential for dimer formation in solution and receptor binding. We detected weak binding of LukH, but not LukG, to the cellular receptor CD11b by biolayer interferometry, suggesting that in common with other members of this toxin family, the S-component has the primary contact role with the receptor. These new insights provide the basis for novel strategies to counteract this powerful toxin and Staphylococcus aureus pathogenesis.