To improve the quality of chemical vapor deposition (CVD)-prepared hexagonal boron nitride (h-BN), it is essential to understand the growth mechanism, particularly to learn the structures as well as their stabilities and kinetic evolutions of the formed clusters in the initial growth stage. Herein, we performed systematic studies on the stabilities of various geometries of different-/identical-sized BN clusters on (111) surfaces of Ni and Cu by density functional theory simulations. The results show that the stable configurations of different-sized clusters are those containing the most normal hexagons composed with alternate B and N atoms. There exist ultra-stable magic clusters on the (111) surfaces of both the metals. On Ni(111), the geometries of the magic clusters are composed of hexagons arranged in the core-shell structure, while they contain tetragons on the Cu(111) surface. The ultra-high stabilities of the magic clusters can be attributed to the comprehensive effect from the core-shell structure, high symmetry, edged atoms, and adsorption sites. The stable geometries of different-sized clusters as well as magic clusters present the vital roles of metal substrates in CVD-synthesis of h-BN and provide instructive information in improving the quality of h-BN by selecting appropriate metal substrates.