We explore the non-relativistic string theory (NRST) limit of type II string theory and its action on gravitational solitons. As a start, we exhibit in detail that the NRST limit is T-dual to a discrete lightcone limit and can be viewed as a near-BPS limit. This also clarifies the nature of multi-string states of NRST and its connection to matrix string theory. We consider the NRST limit of the fundamental string soliton, confirming the recent finding that it corresponds to a relativistic near-horizon background, which we argue is the manifestation of a strong coupling phase of the NRST worldsheet theory. Furthermore, we consider the NRST limit of a class of D-branes as well as the NS5-brane. This reveals that they become gravitational solitons in NRST, as they are sourced torsional string Newton-Cartan (TSNC) geometries. Finally, for the NRST D-brane solitons we show that a further decoupling limit leads to new holographic correspondences between multicritical matrix theories and NRST in curved TSNC backgrounds.