Conventional epitaxy of semiconductor films requires a compatible single crystalline substrate and precisely controlled growth conditions, which limit the price competitiveness and versatility of the process. We demonstrate substrate-tolerant nano-heteroepitaxy (NHE) of high-quality formamidinium-lead-tri-iodide (FAPbI ) perovskite films. The layered perovskite templates the solid-state phase conversion of FAPbI from its hexagonal non-perovskite phase to the cubic perovskite polymorph, where the growth kinetics are controlled by a synergistic effect between strain and entropy. The slow heteroepitaxial crystal growth enlarged the perovskite crystals by 10-fold with a reduced defect density and strong preferred orientation. This NHE is readily applicable to various substrates used for devices. The proof-of-concept solar cell and light-emitting diode devices based on the NHE-FAPbI showed efficiencies and stabilities superior to those of devices fabricated without NHE.