As the solidified microstructures have a significant influence on the corrosion behavior, our aim is to derive the optimum microstructures and electrochemical conditions for producing Mo nanowires. Eutectic microstructures showing coupling growth of NiAl phase and Mo fibers were obtained at growth rates from 10 to 40 μm/s. The fiber size varies from 800 nm to 300 nm, and decreases with the increase of solidification rate. Potentiodynamic polarization studies indicated that NiAl-Mo alloy at a growth rate of 20 μm/s has a better corrosion resistance in 0.1 M HCl solution at room temperature. The electrochemical corrosion behavior of directionally solidfied NiAl-Mo alloys not only depends on fiber size, but also related to the interface morphology. To further analyze the influence of interface morphology on the corrosion behavior, velocity suddenly change experiments were carried out. The microstructure of directionally solidified NiAl-Mo alloy transformed from planar to cellular and dendritic structures as the value of V/V1 increased. The results of potentiodynamic polarization curves revealed that the planar structure has the highest corrosion resistance compared to other mophologies with the same fiber size of Mo-nanowires.