We demonstrate methods to improve the crystalline-quality of free-standing Bi nanowires arrays on a Si substrate and enhance the preferred trigonal orientation for thermoelectric performance by annealing the arrays above the 271.4 °C Bi melting point. The nanowires maintain their geometry during melting due to the formation of a thin Bi-oxide protective shell that contains the molten Bi. Recrystallizing nanowires from the melt improves crystallinity; those cooled rapidly demonstrate a strong trigonal orientation preference.