The pulsar wind nebula (PWN) 3C 58 has been proposed as a good candidate for detection at VHE (VHE; E>100 GeV) for many years. It is powered 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 its morphology. This object was previously observed by imaging atmospheric Cherenkov telescopes (Whipple, VERITAS and MAGIC), and 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. 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 according to GALPROP, 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 gamma-ray emission.