The pulsar wind nebula (PWN) 3C 58 is one of the historical very-high-energy (VHE; E>100 GeV) gamma-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 to the Crab Nebula due to their morphological similarities. This object was previously observed by imaging atmospheric Cherenkov telescopes (Whipple, VERITAS and MAGIC), although not detected, with an upper limit of 2.4% Crab Unit (C.U.) at VHE. It was detected by Fermi-LAT with a spectrum extending beyond 100 GeV. We analyzed 81 hours of 3C 58 data taken with the MAGIC telescopes and we detected VHE gamma-ray emission with a significance of 5.7 sigma and an integral flux of 0.65% C.U. above 1 TeV. The differential energy spectrum between 400 GeV and 10 TeV is well described by a power-law function dphi/dE=f_0(E/1TeV)^{-Gamma} with f_0=(2.0pm0.4_{stat}pm0.6_{sys})times10^{-13}cm^{-2}s^{-1}TeV^{-1} and Gamma=2.4pm0.2_{stat}pm0.2_{sys}. The skymap is compatible with an unresolved source. We report the first significant detection of PWN 3C 58 at TeV energies. According to our results 3C 58 is the least luminous VHE gamma-ray PWN ever detected at VHE and the one with the lowest flux at VHE to date. We compare our results with the expectations of time-dependent models in which electrons up-scatter photon fields. The best representation favors a distance to the PWN of 2 kpc and Far Infrared (FIR) comparable to CMB 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 unrealistic energy budget given the density of the medium, disfavoring cosmic ray acceleration in the SNR as origin of the VHE gamma-ray emission.