We have used mixed quantum classical molecular dynamics simulations to explore the role of structural relaxation when binding an excess electron to neutral water clusters. The structural and spectral properties of the water cluster anions were investigated as a function of the size (n = 45 and 104), nominal temperature (T-nom = 50, 100, and 150 K), and preparation method of the parent neutral clusters. In particular, we consider two different protocols for preparing the initial neutral clusters, which differ markedly in their thermal history. In the first, warm equilibrium neutral clusters are gradually quenched to increasingly lower temperature. In the second, neutral clusters are formed spontaneously at similar to 0 K and then warmed to the same target temperatures, yielding inherently metastable, nonequilibrium structures. Electron attachment to these alternative sets of clusters shows that below a critical temperature (similar to 200 K), the metastable water clusters bind a surface state excess electron significantly more strongly than the quenched, equilibrium clusters. The structural analysis indicates that these cluster anions with larger vertical detachment energies (VDEs) more frequently stabilize the electron by double-acceptor-type water molecules and exhibit a weak temperature dependence of the VDE compared with the quenched clusters. These results suggest that the alternative classes of cluster anions seen experimentally may reflect differences in the thermal history of such clusters.