Magnetic proximity effect at the interface between magnetic and topological insulators (MIs and TIs) is considered to have great potential in spintronics as, in principle, it allows realizing the quantum anomalous Hall and topological magneto-electric effects (QAHE and TME). Although an out-of-plane magnetization induced in a TI by the proximity effect was successfully probed in experiments, first-principles calculations reveal that a strong electrostatic potential mismatch at abrupt MI/TI interfaces creates harmful trivial states rendering both the QAHE and TME unfeasible in practice. Here on the basis of recent progress in formation of planar self-assembled single layer MI/TI heterostructure (T. Hirahara et al. Nano Lett. 2017 , 17 , 3493 - 3500 ), we propose a conceptually new type of the MI/TI interfaces by means of density functional theory calculations. By considering MnSe/Bi2Se3, MnTe/Bi2Te3, and EuS/Bi2Se3 we demonstrate that, instead of a sharp MI/TI interface clearly separating the two subsystems, it is energetically far more favorable to form a built-in interface via insertion of the MI film inside the TI's surface quintuple layer (e.g., Se-Bi-Se-[MnSe]-Bi-Se) where it forms a bulk-like MI structure. This results in a smooth MI-to-TI connection that yields the interface electronic structure essentially free of trivial states. Our findings open a new direction in studies of the MI/TI interfaces and restore their potential for the QAHE and TME observation.