Nano-crystalline Ni and Cu films deposited on the r-plane of sapphire (alpha-Al2O3) develop a <1 1 1> fiber-texture upon annealing, in which grains grow up to 300 to 500 times larger than the film thickness. Most of the largest grains, which have grown at the expense of others, display one of four preferred orientation relationships (ORs) to the substrate. The four preferred ORs are OR1r = Me(1 1 1)[1 (1) over bar 0]//alpha-Al2O3(1 (1) over bar 0 2)[1 1 (2) over bar 0], OR2r = Me(1 1 1)[1 (1) over bar 0]//alpha-Al2O3(1 (1) over bar 0 2)[(1) over bar 1 0 1] (Me = Ni or Cu), and their twins, which are rotated 60 degrees about the <1 1 1> axis perpendicular to the substrate. For these ORs, one of the densest <1 1 0> atomic rows that lies within the Me {1 1 1} interfacial plane, aligns with the direction of the step edges that form at the intersection of the r-plane with one of its neighboring facets on the equilibrium shape of sapphire (i.e. the c(0001), p-{1 1 (2) over bar 3} or s{1 0 (1) over bar 1}-planes). One of the ORs is most preferred when the steps at the interface are such that a {1 0 0}-type ledge of the Me {1 1 1} interfacial plane faces the ledge of the sapphire step. This observation provides a useful insight into the origin of the preferred ORs, and confirms the important role of surface steps in texture development. The evolution of Ni films of different thicknesses, ranging from 100 to 560 nm, was analyzed. Grain boundary grooving inhibits grain boundary motion and favors hole formation and dewetting in the thinnest films (100 nm). The crystals left behind after dewetting display ORs which may differ from the preferred ones. Large grains with the preferred ORs can grow at the expense of others when the film thickness is greater than 300 nm.