We find a Polyakov-type action for strings moving in a torsional Newton-Cartan geometry. This is obtained by starting with the relativistic Polyakov action and fixing the momentum of the string along a non-compact null isometry. For a flat target space, we show that the world-sheet theory becomes the Gomis-Ooguri action. From a target space perspective these strings are non-relativistic but their world-sheet theories are still relativistic. We show that one can take a scaling limit in which also the world-sheet theory becomes non-relativistic with an infinite-dimensional symmetry algebra given by the Galilean conformal algebra. This scaling limit can be taken in the context of the AdS/CFT correspondence and we show that it is realized by the ‘Spin Matrix Theory’ limits of strings on AdS5 × S5. Spin Matrix theory arises as non-relativistic limits of the AdS/CFT correspondence close to BPS bounds. The duality between non-relativistic strings and Spin Matrix theory provides a holographic duality of its own and points towards a framework for more tractable holographic dualities whereby non-relativistic strings are dual to near BPS limits of the dual field theory.