The duality between theories of quantum strings and Yang-Mills gauge theories, in particular the AdS/CFT conjecture, has over the years given rise to many important physical insights. Recently, the realization that both sides of the duality, in certain limits, can be be described by integrable systems has lead to a good deal of progress. In this talk we will review the construction of these integrable structures and their usefulness in understanding strings in curved backgrounds/strongly coupled gauge theories. We will discuss how the asymptotic S-matrix that enters the Bethe equations for gauge theory anomalous dimensions provides a very convenient description of the system and how it can be reproduced from the classical string theory. Further, we will outline some partial attempts to extend this equivalence, and the corresponding integrable structures, to include world-sheet quantum loop effects.