The hydroxide ion (OH-) has an unusually high mobility in water. comparable to that of the proton. However, a consensus view of the OH- mobility mechanism and its solvation structure has yet to emerge. In addition, X-ray and spectroscopic experiments reveal significant changes in the structural and dynamical properties of water in the presence of OH-. To gain insight into these questions. we have carried out Car-Parrinello molecular dynamics (CPMD) calculations for aqueous NaOH and KOH solutions under ambient conditions over a wide range of concentrations. These simulations are able to reproduce many puzzling phenomena, in particular, the loss of tetrahedral coordination of water (interpreted from a recent neutron diffraction with isotopic substitution experiment) and the appearance of new spectroscopic features at high concentrations. Furthermore, it is demonstrated that the observed behavior is a result of the fort-nation of a variety of compact hydroxide-water complexes. The distribution of these complexes is dependent upon the concentration and the counterion. The present results reconcile conflicting structural interpretations from previous experimental and theoretical studies on hydroxide solutions. Analysis of the CPMD trajectories supports the view that the transport mechanism of the hydroxide ion is distinct from that of the proton.