The epoch of first star formation in the early Universe was dominated by simple atomic and molecular species consisting mainly of two elements: hydrogen and helium. Gaining insight into this constitutive era requires a thorough understanding of molecular reactivity under primordial conditions. We used a cryogenic ion storage ring combined with a merged electron beam to measure state-specific rate coefficients of dissociative recombination, a process by which electrons destroy molecular ions. We found a pronounced decrease of the electron recombination rates for the lowest rotational states of the helium hydride ion (HeH+), compared with previous measurements at room temperature. The reduced destruction of cold HeH+ translates into an enhanced abundance of this primordial molecule at redshifts of first star and galaxy formation.