Topological insulators(1-8) are a novel form of matter which features metallic surface states with quasirelativistic dispersion similar to graphene(9). Unlike graphene, the locking of spin and momentum and the protection by time-reversal symmetry(1-8) open up tremendous additional possibilities for external control of transport properties(10-18). Here we show by angle-resolved photoelectron spectroscopy that the topological sur-face states of Bi2Te3 and Bi2Se3 are stable against the deposition of Fe without opening a band gap. This stability extends to low submonolayer coverages meaning that the band gap reported recently(19) for Fe on Bi2Se3 is incorrect as well as to complete monolayers meaning that topological surface states can very well exist at interfaces with ferromagnets in future devices.