Inspired by recent connections between spectral theory and topological string theory, we propose exact quantization conditions for the relativistic Toda lattice of N particles. These conditions involve the Nekrasov-Shatashvili free energy, which resums the perturbative WKB expansion, but they require in addition a non-perturbative contribution, which is related to the perturbative result by an S-duality transformation of the Planck constant. We test the quantization conditions against explicit calculations of the spectrum for N = 3. Our proposal can be generalized to arbitrary toric Calabi-Yau manifolds and might solve the corresponding quantum integrable system of Goncharov and Kenyon.