The $mathbf{O}(D,D)$ covariant generalized metric, postulated as a truly fundamental variable, can describe novel geometries where the notion of Riemannian metric ceases to exist. Here we quantize a closed string upon such backgrounds and identify flat, anomaly-free, non-Riemannian string vacua in the familiar critical dimension, $D{=26}$ (or $D{=10}$). Remarkably, the whole BRST closed string spectrum is restricted to just one level with no tachyon, and matches the linearized equations of motion of Double Field Theory. Taken as an internal space, our non-Riemannian vacua may open up novel avenues alternative to traditional string compactification.