Anionic states of nucleic acid bases are involved in DNA damage by low-energy electrons and in charge transfer through DNA. Previous gas phase studies of free, unsolvated nucleic acid base parent anions probed only dipole-bound states, which are not present in condensed phase environments, but did not observe valence anionic states, which for purine bases are thought to be adiabatically unbound. Contrary to this expectation, we have demonstrated that some thus far ignored tautomers of adenine, which result from enamine-imine transformations, support valence anionic states with electron vertical detachment energies as large as 2.2 eV, and at least one of these anionic tautomers is adiabatically bound. Moreover, we predict that the new anionic tautomers should also dominate in solutions and should be characterized by larger values of electron vertical detachment energy than the canonical valence anion. All of the newfound anionic tautomers might be formed in the course of dissociative electron attachment followed by a hydrogen atom attachment to a carbon atom, and they might affect the structure and properties of DNA and RNA exposed to low-energy electrons. The new valence states observed here, unlike the dipole-bound state, could exist in condensed phases and might be relevant to radiobiological damage. The discovery of these valence anionic states of adenine was facilitated by the development of (i) an experimental method for preparing parent anions of nucleic acid bases for photoelectron experiments, and (ii) a combinatorial/quantum chemical approach for identification of the most stable tautomers of organic molecules.