A simple metallurgical process for fabricating oxide nano-rod array structures via internal oxidation is described. Some dilute alloys such as Ni(Al) and Fe(Al) solid solutions develop rod-like oxide precipitates after their internal oxidation at high-temperatures and under low oxygen partial pressures. The oxide nano-rod array structure can be developed on the metal substrate by removing the metallic matrix of the internal oxidation zone. Al2O3 or MAl2O4 (M=Ni or Fe) spinel nano-rod array structures were prepared by using M(Al) solid solutions. Pack cementation process to develop M(Al) solid solution surface layers was used for the fabrication of nano-rod array structures on substrates with desired shape. Near-net shape Ni substrates with oxide nano-rod array structures on their surfaces can be prepared by using pack cementation and internal oxidation.