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 Bi$_2$Te$_3$ and Fe$_3$O$_4$. By growing two different types of heterostructures by molecular beam epitaxy, Fe$_3$O$_4$ on Bi$_2$Te$_3$ and Bi$_2$Te$_3$ on Fe$_3$O$_4$, we explore differences in chemical stability, crystalline quality, electronic structure, and transport properties. We find the heterostructure Bi$_2$Te$_3$ on Fe$_3$O$_4$ to be a more viable approach, with transport signatures in agreement with a gap opening in the topological surface states.