Relying on the magnetism induced by the proximity effect in heterostructures of topological insulators and magnetic insulators is one of the promising routes to achieve the quantum anomalous Hall effect. Here, we investigate heterostructures of Bi2Te3 and Fe3O4. By growing two different types of heterostructures by molecular beam epitaxy, Fe3O4 on Bi2Te3 and Bi2Te3 on Fe3O4, we explore differences in chemical stability, crystalline quality, electronic structure, and transport properties. We find the heterostructure Bi2Te3 on Fe3O4 to be a more viable approach, with transport signatures in agreement with a gap opening in the topological surface states.