Motivated by an amazing range of reported distances to the nearby Local Group spiral galaxy M33, we have obtained deep near-infrared photometry for 26 long-period Cepheids in this galaxy with the ESO VLT. From the data we constructed period-luminosity relations in the J and K bands which together with previous optical VI photometry for the Cepheids by Macri et al. were used to determine the true distance modulus of M33, and the mean reddening affecting the Cepheid sample with the multiwavelength fit method developed in the Araucaria Project. We find a true distance modulus of 24.62 for M33, with a total uncertainty of +- 0.07 mag which is dominated by the uncertainty on the photometric zero points in our photometry. The reddening is determined as E(B-V)=0.19 +- 0.02, in agreement with the value used by the HST Key Project of Freedman et al. but in some discrepancy with other recent determinations based on blue supergiant spectroscopy and an O-type eclipsing binary which yielded lower reddening values. Our derived M33 distance modulus is extremely insensitive to the adopted reddening law. We show that the possible effects of metallicity and crowding on our present distance determination are both at the 1-2% level and therefore minor contributors to the total uncertainty of our distance result for M33.