Hydroxide (OH-) ions at or near the interface between water and titanium dioxide (TiO2) have an important role in many surface photocatalytic reactions, possibly including the photo-oxidation of water. Using first principles molecular dynamics (FPMD) simulations on the time scale of 30-40 ps, we have investigated the structure and electronic properties of a solvated or adsorbed OH at the interface between liquid water and a stoichiometric anatase TiO2(101) slab. We observed that a solvated hydroxide ion diffuses spontaneously from bulk water toward the anatase surface, a result consistent with the known point of zero charge for TiO2 in water. The O atom of the adsorbed OH-forms two H-bonds with nearby water molecules, whereas three to four bonds are typically found for OH- solvated in bulk water. Analysis of the interface electronic structure along the FPMD trajectories shows significant differences in the densities of states of different atomic configurations, indicating that thermal fluctuations have an important effect on the electronic energy levels. In particular, while the topmost occupied levels of OH- (water) typically lie below (well below) the TiO2 valence band edge (VBE), thermal fluctuations can lead to special, poorly solvated configurations where the topmost OH- energy levels are above the TiO2 VBE. In these configurations, holes generated by UV light absorption can be transferred from the anatase surface to the adsorbed hydroxide ion, though such transfer is usually forbidden.