We prove that a large class of leading order string solutions which generalize both the plane-wave and fundamental string backgrounds are, in fact, exact solutions to all orders in \alpha'. These include, in particular, the traveling waves along the fundamental string. The key features of these solutions are a null symmetry and a chiral coupling of the string to the background. Using dimensional reduction, one finds that the extremal electric dilatonic black holes and their recently discovered generalizations with NUT charge and rotation are also exact solutions. We show that our bosonic solutions are also exact solutions of the heterotic string theory with no extra gauge field background.