We perform quantitative analysis of the X-ray absorption data taken in situ during the earliest cycles of the ZnO atomic layer deposition on atomically flat InGaAs (001) surfaces. As deposition progresses, we observe a transition from an amorphous structure to a nanocrystalline one. The former retains much of the characteristics of a ZnO crystal in the Zn coordination shell, while the latter shows atomic ordering up to at least the third neighbor shell of Zn atoms, despite the absence of Bragg X-ray diffraction peaks. We show that the different chemical preparation of the substrate surface affects the ZnO local structure and that, counterintuitively, a stronger short-range order is obtained in the nanostructures characterized by lower local order at the interface. We propose a model that accounts for these findings.