We have investigated iron-doped rutile TiO2 in great detail by density functional theory (DFT) calculations. The influence of the Fe dopants on the structural and electronic properties are calculated. Three different dopant models are considered in this study, where iron is present in Fe(II), Fe(III), and Fe(IV) oxidation states. Our results indicate that the configuration of Fe(III), where two neighboring Ti sites are replaced by Fe dopants and an O vacancy locates in between, is the lowest-energy structure. The resulting Mossbauer signatures are in excellent agreement with the available experimental literature data, thus supporting the proposed structural model. Although the crystal structure of doped rutile is not significantly altered, even for larger concentrations of dopant atoms, the local structure around Fe atoms can be strongly distorted, especially due to the presence of oxygen vacancies. Fe doping lowers the band gap and introduces midgap states.