We report a detailed investigation of the first stages of the growth of self-organized Fe clusters on the reconstructed Au(111) surface by grazing incidence X-ray diffraction. Below one monolayer coverage, the Fe clusters are in local epitaxy whereas the subsequent layers adopt first a strained fcc lattice and then a partly relaxed bcc(110) phase in a Kurdjumov-Sachs epitaxial relationship. The structural evolution is discussed in relation with the magnetic properties of the Fe clusters.