Phosphorene, a new two-dimensional (2D) semiconductor, has received much interest due to its robust direct band gap and high charge mobility. Currently, however, phosphorene can only be produced by mechanical or liquid exfoliation, and it is still a significant challenge to directly epitaxially grow phosphorene, which greatly hinders its mass production and, thus, applications. In epitaxial growth, the stability of nanoscale cluster or flake on a substrate is crucial. Here, we perform ab initio energy optimizations and molecular dynamics simulations to explore the critical role of substrate on the stability of a representative phosphorene flake. Our calculations show that the stability of the phosphorene nanoflake is strongly dependent on the interaction strength between the nanoflake and substrate. Specifically, the strong interaction (0.75 eV/P atom) with Cu(111) substrate breaks up the phosphorene nanoflake, while the weak interaction (0.063 eV/P atom) with h-BN substrate fails to stabilize its 2D structure. Remarkably, we find that a substrate with a moderate interaction (about 0.35 eV/P atom) is able to stabilize the 2D characteristics of the nanoflake on a realistic time scale. Our findings here provide useful guidelines for searching suitable substrates for the directly epitaxial growth of phosphorene.