Here we report the first mass spectrometric study of negative ions formed via free electron attachment (EA) to nucleobases (NBs) embedded in helium clusters. Pure and mixed clusters of adenine and thymine have been formed by pickup of isolated NB molecules by cold helium droplets. In contrast to EA of isolated molecules in the gas phase we observe a long-lived parent anion NB- and, in addition, parent cluster ions NB-n up to size n=6. Moreover, we show that a low energy electron penetrating into a doped helium droplet causes efficient damage of the embedded nucleobases via resonant, site selective, dissociative electron attachment.