Among various photocatalytic materials, Z-scheme photocatalysts have drawn tremendous research interest due to the high photocatalytic performance in solar water splitting. Here, we perform extensive hybrid density functional theory calculations to explore electronic structures, interfacial charge transfer, electrostatic potential profile, optical absorption properties, and photocatalytic properties of a proposed two-dimensional small-lattice-mismatched GaTe/Bi2Se3 heterostructure. Theoretical results clearly reveal that the examined heterostructure with a small direct band gap can effectively harvest the broad spectrum of the incoming sunlight. Due to the relative strong interfacial built-in electric field in the heterostructure and the small band gap between the valence band maximum of GaTe monolayer and the conduction band minimum of Bi2Se3 nanosheet with slight band edge bending, the photogenerated carriers transfer via Z-scheme pathway, which results in the photogenerated electrons and holes effectively separating into the GaTe monolayer and the Bi2Se3 nanosheet for the hydrogen and oxygen evolution reactions, respectively. Our results imply that the artificial 2D GaTe/Bi2Se3 is a promising Z-scheme photocatalyst for overall solar water splitting.