We have carried out a narrow-band survey of the Local Group galaxy, M 33, in the HeII lambda4686 emission line, to identify HeII nebulae in this galaxy. With spectroscopic follow-up observations, we confirm three of seven candidate objects, including identification of two new HeII nebulae, BCLMP651, HBW673. We also obtain spectra of associated ionizing stars for all the HII regions, identifying two new WN stars. We demonstrate that the ionizing source for the known HeII nebula, MA 1, is consistent with being the early-type WN star MC8 (M 33-WR14), by carrying out a combined stellar and nebular analysis of MC8 and MA 1. We were unable to identify the helium ionizing sources for HBW 673 and BCLMP 651, which do not appear to be Wolf-Rayet stars. According to the [OIII]lambda5007/Hbeta vs. [NII]lambda6584/Halpha diagnostic diagram, excitation mechanisms apart from hot stellar continuum are needed to account for the nebular emission in HBW 673, which appears to have no stellar source at all.