We have studied the epitaxial growth of GaSe, a layered van der Waals material, on GaAs, a zinc-blende-structure semiconductor. This heterostructure exhibits a 6% lattice mismatch, and is a prototypical example of van der Waals epitaxy, where the weak van der Waals interaction allows the misfit to be accommodated without the formation of electronically active defects. GaSe was supplied to the growing surface from a single GaSe Knudsen cell. Reflection high energy electron diffraction and x-ray photoemission spectroscopy studies of the nucleation of GaSe indicate Se reacts with the GaAs surface to remove the surface dangling bonds prior to GaSe formation. This is followed by the oriented growth of stoichiometric GaSe layers, that are rotationally aligned with the underlying GaAs substrate. The termination of the GaAs dangling bonds most likely occurs by Se substitution for As in the surface layer of GaAs(lll) B and by direct bonding of Se to surface Ga on GaAs(lll) A surfaces. In addition, photoemission measurements indicate that the subsurface Se uptake into the GaAs(lll) A lattice is higher than that in the (111) B lattice.