We report the first preparation of small gold–nickel (AuNi) bimetallic nanoparticles (<5 nm) supported on titania by the method of galvanic replacement reaction (GRR), evidenced by the replacement of Ni atoms by Au atoms according to the stoichiometry of the reaction. We showed that this preparation method allowed not only the control of the gold and nickel contents in the samples, but also the formation of small bimetallic nanoparticles with strained core–shell structures, as revealed by aberration-corrected scanning transmission electron microscopy in combination with energy-dispersive X-ray spectroscopy mapping. The catalytic characterization by the probe reaction of semi-hydrogenation of butadiene showed that the resulting nickel-based nanocatalysts containing a small amount of gold exhibited higher selectivity to butenes than pure nickel catalysts and a high level of activity, closer to that of pure nickel catalysts than to that of pure gold catalysts. These improved catalytic performances could not be explained by a mere structural model of simple core–shell structure of the nanoparticles. Instead, they could come from the incorporation of Ni within the gold surface and/or from surface lattice relaxation and subsurface misfit defects.