Binding of hexokinase HKI to mitochondrial voltage-dependent anion channels (VDACs) has far-reaching physiological implications. However, the structural basis of this interaction is unclear. Combining computer simulations with experiments in cells, we here show that complex assembly relies on intimate contacts between the N-terminal alpha-helix of HKI and a charged membrane-buried glutamate on the outer wall of VDAC1 and VDAC2. Protonation of this residue blocks complex formation in silico while acidification of the cytosol causes a reversable release of HKI from mitochondria. Membrane insertion of HKI occurs adjacent to the bilayer-facing glutamate where a pair of polar channel residues mediates a marked thinning of the cytoplasmic leaflet. Disrupting the membrane thinning capacity of VDAC1 dramatically impairs its ability to bind HKI in silico and in cells. Our data reveal key topological and mechanistic insights into HKI-VDAC complex assembly that may benefit the development of therapeutics to counter pathogenic imbalances in this process.