This work describes a novel fabrication method of single crystalline Mo nanowires and nanowire arrays. The method utilizes directional solidification (ds) of a NiAl-Mo eutectic alloy and its subsequent electrochemical processing. In the first step, a self-organized array of Mo nanowires embedded in a NiAl matrix is obtained. By combining the Pourbaix diagrams of the three elements involved, a strategy for selective removal of either of the two phases is derived. An oxidizing acidic solution of pH 0.2 dissolved the matrix and released an array of long and uniform Mo wires. Even a complete extraction of the wires is possible through entire dissolution of the matrix. On the other hand, electrodissolution of the Mo with a simultaneous passivation of the NiAl matrix at the pH 6 and the potential of 200 mV SHE yielded nanopore arrays with rectangular pores. This method has several advantages. First of all, it is one of the few top-down methods that allow the production of large amounts of nanostructures. In addition, both the wires and the matrix are single crystalline which makes them favorable for various applications. Further, the obtained nanostructures exhibit extremely high aspect ratios (> 1000), unreachable by most other techniques. This technique has the potential for the production of nanowire arrays either for employment in sensors or in field emission.