Car-Parrinello molecular dynamics simulations have been carried out for aqueous NaOH and KOH solutions under ambient conditions over a wide range of concentrations. From these simulations, we have observed a continuous change of the water structure with added hydroxide, characterized by a significant shift of the second peak of the OO radial distribution functions to shorter distances. At the highest concentration investigated, the normal tetrahedral coordination of pure water is completely missing, a result that is consistent with a recent neutron diffraction experiment. The added hydroxide also gives rise to some unique spectroscopic features, including a "free" O-H stretch, a broadening of the normal water OH stretching band, and a large blue shift of both the librational band and the low-frequency translation. These results are in good agreement with the experimental data. Finally, it was demonstrated that the structural and dynamical behavior is inextricably linked to the formation of compact hydroxide-water complexes.