The formation and stability of Ni and V nanowires on a stepped Rh(553) substrate is investigated using the BFS method for alloys via an atom-by-atom description of the formation process. In agreement with experiment, Ni is found to form one-dimensional wires attached to the surface steps, while V does not. However, a detailed analysis of the energetics reveals that there the apparent differences leave room for the possibility of alloying in the case of Ni and the formation of structures along the step in the case of V.