By a combination of high-resolution imaging and grazing-incidence x-ray diffraction at the GaAs(001)-CdTe(111) heterostructure we solve the atomic structure at the interface. We measure a square-root2(2x9) reconstructed unit cell and show that only three monolayers are involved in the interface relaxation. We deduce the first nearest neighbors of each atomic species at the interface and describe how they differ from the initial adsorbed layer on a bare GaAs(001) surface. This structure is compatible with two electrons per bond at any atom.