The number of known very high energy (VHE) blazars is ~50, which is very small in comparison to the number of blazars detected in other frequencies. This situation is a handicap for population studies of blazars, which emit about half of their luminosity in the γ-ray domain. Moreover, VHE blazars, if distant, allow for the study of the environment that the high-energy γ-rays traverse in their path towards the Earth, like the extragalactic background light (EBL) and the intergalactic magnetic field (IGMF), and hence they have a special interest for the astrophysics community. We present the first VHE detection of 1ES 0033+595 with a statistical significance of 5.5σ. The VHE emission of this object is constant throughout the MAGIC observations (2009 August and October), and can be parametrized with a power law with an integral flux above 150 GeV of (7.1 ± 1.3) × 10-12 photons cm-2 s-1 and a photon index of (3.8 ± 0.7). We model its spectral energy distribution (SED) as the result of inverse Compton scattering of synchrotron photons. For the study of the SED, we used simultaneous opticalR-band data from theKVAtelescope, archival X-ray data by Swift as well as INTEGRAL, and simultaneous high-energy (HE, 300 MeV-10 GeV) γ-ray data from the Fermi Large Area Telescope (LAT) observatory. Using the empirical approach of Prandini et al. (2010) and the Fermi LAT and MAGIC spectra for this object, we estimate the redshift of this source to be 0.34 ± 0.08 ± 0.05. This is a relevant result because this source is possibly one of the 10 most distant VHE blazars known to date, and with further (simultaneous) observations could play an important role in blazar population studies, as well as future constraints on the EBL and IGMF.