Topological insulators are new states of matter with a bulk gap and robust gapless surface states protected by time-reversal symmetry. When time-reversal symmetry is broken, the surface states are gapped, which induces a topological response of the system to electromagnetic field--the topological magnetoelectric effect. In this paper we study the behavior of topological surface states in heterostructures formed by a topological insulator and a magnetic insulator. Several magnetic insulators with compatible magnetic structure and relatively good lattice matching with topological insulators ${\rm Bi_2Se_3}, {\rm Bi_2Se_3}, {\rm Sb_2Te_3}$ are identified, and the best candidate material is found to be MnSe, an anti-ferromagnetic insulator. We perform first-principles calculation in ${\rm Bi_2Se_3/MnSe}$ superlattices and obtain the surface state bandstructure. The magnetic exchange coupling with MnSe induces a gap of $∼$54 meV at the surface states. In addition we tune the distance between Mn ions and TI surface to study the distance dependence of the exchange coupling. ; Comment: 8 pages, 7 figures