A combined experimental and theoretical study of doping individual Fe atoms into Bi2Se3 is presented. It is shown through a scanning tunneling microscopy study that single Fe atoms initially located at hollow sites on top of the surface (adatoms) can be incorporated into subsurface layers by thermally activated diffusion. Angle-resolved photoemission spectroscopy in combination with ab initio calculations suggest that the doping behavior changes from electron donation for the Fe adatom to neutral or electron acceptance for Fe incorporated into substitutional Bi sites. According to first principles calculations within density functional theory, these Fe substitutional impurities retain a large magnetic moment, thus presenting an alternative scheme for magnetically doping the topological surface state. For both types of Fe doping, we see no indication of a gap at the Dirac point. DOI: 10.1103/PhysRevLett.110.126804