Out-of-plane Ga2Se3 nanowires are grown by molecular beam epitaxy via Au-assisted heterovalent exchange reaction on GaAs substrates in the absence of Ga deposition. It is shown that at a suitable temperature around 560 °C the Au-decorated GaAs substrate releases Ga atoms, which react with the incoming Se and feed the nanowire growth. The nanowire composition, crystal structure, and morphology are characterized by Raman spectroscopy and electron microscopy. The growth mechanism is investigated by X-ray photoelectron spectroscopy. We explore the growth parameter window and find an interesting effect of shortening of the nanowires after a certain maximum length. The nanowire growth is described within a diffusion transport model, which explains the nonmonotonic behavior of the nanowire length versus the growth parameters. Nanowire shortening is explained by the blocking of Ga supply from the GaAs substrate by thick, in-plane worm-like Ga2Se3 structures, which grow concomitantly with the nanowires, followed by backward diffusion of Ga atoms from the nanowires down to the substrate surface.