To realize spintronic devices based on topological insulators (TIs), well-defined interfaces between magnetic metals and TIs are required. Here, we characterize atomically precisely the interface between the 3d transition metal Fe and the TI Bi2Te3 at different stages of its formation. Using photoelectron diffraction and holography, we show that after deposition of up to 3 monolayers Fe on Bi2Te3 at room temperature, the Fe atoms are ordered at the interface despite the surface disorder revealed by our scanning-tunneling microscopy images. We find that Fe occupies two different sites: a hollow adatom deeply relaxed into the Bi2Te3 quintuple layers and an interstitial atom between the third (Te) and fourth (Bi) atomic layers. For both sites, our core-level photoemission spectra and density-functional theory calculations demonstrate simultaneous chemical bonding of Fe to both Te and Bi atoms. We further show that upon deposition of Fe up to a thickness of 20 nm, the Fe atoms penetrate deeper into the bulk forming a 2-5 nm interface layer containing FeTe. In addition, excessive Bi is pushed down into the bulk of Bi2Te3 leading to the formation of septuple layers of Bi3Te4 within a distance of ∼25 nm from the interface. Controlling the magnetic properties of the complex interface structures revealed by our work will be of critical importance when optimizing the efficiency of spin injection in TI-based devices.