In recent years, van der Waals heterostructures (vdWHs) with controllable and peculiar properties have attracted extensive attention in the fields of electronics, optoelectronics, spintronics and electrochemistry. However, vdWHs with good thermoelectric performance are few due to the complex coupling of thermoelectric coefficients. Here, we employ density functional theory and Boltzmann's transport equation to explore the thermoelectric properties of the p-n vdWH of GaSe/SnS2, which has been experimentally observed to exhibit high performance as an optoelectronic device. We reveal that GaSe/SnS2 possesses strong anisotropy in terms of electronic transport resulting from the anisotropic carrier relaxation time. The longer carrier relaxation time in the y-direction for n-type induces a high power factor of 0.084 W m-1 K-2 at 300 K, while it is only 0.0087 W m-1 K-2) in the x-direction. The strong coupling of low-mid frequency phonon branches and the relatively weak Sn-S bond-induced anharmonicity hinder the phonon transport, which results in the lattice thermal conductivity of GaSe/SnS2 (14.61 and 15.43 W m-1 K-1 along the x- and y-directions at 300 K) being much smaller than the average value of GaSe and SnS2 (43.44 W m-1 K-1 at 300 K). The optimal thermoelectric figure of merit at 700 K for GaSe/SnS2 reaches 2.99, which is significantly higher than those of the constituents of GaSe (0.58) and SnS2 (1.04). The present work highlights the potential thermoelectric applications and the understanding of the thermoelectric transport mechanism for the recently synthesized p-n vdWH of GaSe/SnS2 with a high thermoelectric figure of merit and strong anisotropy.