Context: The detection of gamma-rays in the very-high-energy (VHE) range (100 GeV-100 TeV) offers the possibility of studying the parent population of ultrarelativistic particles found in astrophysical sources, so it is useful for understanding the underlying astrophysical processes in nonthermal sources. Aim: The discovery of the VHE gamma-ray source HESS J1507-622 is reported and possibilities regarding its nature are investigated. Methods: The H.E.S.S. array of imaging atmospheric Cherenkov telescopes (IACTs) has a high sensitivity compared with previous instruments (~1% of the Crab flux in 25 hours observation time for a 5 sigma point-source detection) and has a large field of view (~5 deg in diameter). HESS J1507-622 was discovered within the ongoing H.E.S.S. survey of the inner Galaxy, and the source was also studied by means of dedicated multiwavelength observations. Results: A Galactic gamma-ray source, HESS J1507-622, located ~3.5 deg from the Galactic plane was detected with a statistical significance > 9 sigma. Its energy spectrum is well fitted by a power law with spectral index Gamma = 2.24 +/- 0.16_{stat} +/- 0.20_{sys} and a flux above 1 TeV of (1.5 +/- 0.4_{stat} +/- 0.3_{sys}) X 10^{-12} cm^{-2} s^{-1}. Possible interpretations (considering both hadronic and leptonic models) of the VHE gamma-ray emission are discussed in the absence of an obvious counterpart.