The main goal of this work is to calculate the contributions to the cosmological recombination spectrum due to bound-bound transitions of helium. We show that due to the presence of helium in the early Universe unique features appear in the total cosmological recombination spectrum. These may provide a unique observational possibility to determine the relative abundance of primordial helium, well before the formation of first stars. We include the effect of the tiny fraction of neutral hydrogen atoms on the dynamics of HeII -> HeI recombination at redshifts $zsim 2500$. As discussed recently, this process significantly accelerates HeII -> HeI recombination, resulting in rather narrow and distinct features in the associated recombination spectrum. In addition this process induces some emission within the hydrogen Lyman-$alpha$ line, before the actual epoch of hydrogen recombination round $zsim 1100-1500$. We also show that some of the fine structure transitions of neutral helium appear in absorption, again leaving unique traces in the Cosmic Microwave Background blackbody spectrum, which may allow to confirm our understanding of the early Universe and detailed atomic physics.