Bimetallic nanostructures with non-random metal atoms distribution are very important for various applications. To synthesize such structures via benign wet chemistry approach remains challenging. This paper reports a synthesis of a Au/Pd alloy nanostructure through the galvanic replacement reaction between Pd ultrathin nanowires (2.4 +/- 0.2 nm in width, over 30 nm in length) and AuCl3 in toluene. Both morphological and structural changes were monitored during the reaction up to 10 h. Continuous changes of chemical composition and crystalline structure from Pd nanowires to Pd68Au32 and Pd45Au55 alloys, and to Au nanoparticles were observed. More interestingly, by using combined techniques such as high-resolution transmission electron microscopy (HRTEM), X-ray diffraction (XRD), energy dispersive X-ray spectrometry (EDS), UV-vis absorption, and extended X-ray absorption fine structure (EXAFS) spectroscopy, we found the formation of Pd68Au32 non-random alloy with Au-rich core and Pd-rich shell, and random Pd45Au55 alloy with uniformly mixed Pd and Au atom inside the nanoparticles, respectively. Density functional theory (DFT) calculations indicated that alkylamine will strongly stabilize Pd to the surface, resulting in diffusion of Au atoms into the core region to form a non-random alloy. We believe such benign synthetic techniques can also enable the large scale preparation of various types of non-random alloys for several technically important catalysis applications.