Context. The pulsar wind nebula (PWN) 3C 58 is one of the historical very high-energy (VHE; E> 100 GeV) γ-ray source candidates. It is energized by one of the highest spin-down power pulsars known (5% of Crab pulsar) and it has been compared with the Crab nebula because of their morphological similarities. This object was previously observed by imaging atmospheric Cherenkov telescopes (Whipple, VERITAS and MAGIC), although it was not detected, with an upper limit of 2.3% Crab unit (C.U.) at VHE. It was detected by the Fermi Large Area Telescope (LAT) with a spectrum extending beyond 100 GeV. Aims: We aim to extend the spectrum of 3C 58 beyond the energies reported by the Fermi Collaboration and probe acceleration of particles in the PWN up to energies of a few tens of TeV. Methods: We analyzed 81 h of 3C 58 data taken in the period between August 2013 and January 2014 with the MAGIC telescopes. Results: We detected VHE γ-ray emission from 3C 58 with a significance of 5.7σ and an integral flux of 0.65% C.U. above 1 TeV. According to our results, 3C 58 is the least luminous VHE γ-ray PWN ever detected at VHE and has the lowest flux at VHE to date. The differential energy spectrum between 400 GeV and 10 TeV is well described by a power-law function dφ/dE = f0(E/1 TeV)-Γ with f0 = (2.0 ± 0.4stat ± 0.6sys) × 10-13 cm-2 s-1 TeV-1 and Γ = 2.4 ± 0.2stat ± 0.2sys. The skymap is compatible with an unresolved source. Conclusions: We report the first significant detection of PWN 3C 58 at TeV energies. We compare our results with the expectations of time-dependent models in which electrons upscatter photon fields. The best representation favors a distance to the PWN of 2 kpc and far-infrared (FIR) values similar to cosmic microwave background photon fields. If we consider an unexpectedly high FIR density, the data can also be reproduced by models assuming a 3.2 kpc distance. A low magnetic field, far from equipartition, is required to explain the VHE data. Hadronic contribution from the hosting supernova remnant (SNR) requires an unrealistic energy budget given the density of the medium, disfavoring cosmic-ray acceleration in the SNR as origin of the VHE γ-ray emission.