Two-dimensional (2D) heterostructures hold the promise for future atomically thin electronics and optoelectronics because of their diverse functionalities. Although heterostructures consisting of different 2D materials with well-matched lattices and novel physical properties have been successfully fabricated via van der Waals (vdW) epitaxy, constructing heterostructures from layered semiconductors with large lattice misfits remains challenging. We report the growth of 2D GaSe/MoSe2 heterostructures with a large lattice misfit using two-step chemical vapor deposition (CVD). Both vertically stacked and lateral heterostructures are demonstrated. The vertically stacked GaSe/MoSe2 heterostructures exhibit vdW epitaxy with well-aligned lattice orientation between the two layers, forming a periodic superlattice. However, the lateral heterostructures exhibit no lateral epitaxial alignment at the interface between GaSe and MoSe2 crystalline domains. Instead of a direct lateral connection at the boundary region where the same lattice orientation is observed between GaSe and MoSe2 monolayer domains in lateral GaSe/MoSe2 heterostructures, GaSe monolayers are found to overgrow MoSe2 during CVD, forming a stripe of vertically stacked vdW heterostructures at the crystal interface. Such vertically stacked vdW GaSe/MoSe2 heterostructures are shown to form p-n junctions with effective transport and separation of photogenerated charge carriers between layers, resulting in a gate-tunable photovoltaic response. These GaSe/MoSe2 vdW heterostructures should have applications as gate-tunable field-effect transistors, photodetectors, and solar cells.