Context. Recently, the high-energy (HE, 0.1–100 GeV) γ-ray emission from the object LMC P3 in the Large Magellanic Cloud (LMC) has been discovered to be modulated with a 10.3-day period, making it the first extra-galactic γ-ray binary. Aim. This work aims at the detection of very-high-energy (VHE, >100 GeV) γ-ray emission and the search for modulation of the VHE signal with the orbital period of the binary system. Methods. LMC P3 has been observed with the High Energy Stereoscopic System (H.E.S.S.); the acceptance-corrected exposure time is 100 h. The data set has been folded with the known orbital period of the system in order to test for variability of the emission. Results. VHE γ-ray emission is detected with a statistical significance of 6.4 σ. The data clearly show variability which is phase-locked to the orbital period of the system. Periodicity cannot be deduced from the H.E.S.S. data set alone. The orbit-averaged luminosity in the 1–10 TeV energy range is (1.4 ± 0.2) × 1035 erg s⁻¹. A luminosity of (5 ± 1) × 1035 erg s⁻¹ is reached during 20% of the orbit. HE and VHE γ-ray emissions are anti-correlated. LMC P3 is the most luminous γ-ray binary known so far.