We introduce a new method, based on alternating optimization, for compact representation of spin Hamiltonians and solution of linear systems of algebraic equations in the tensor train format. We demonstrate the method's utility by simulating, without approximations, a 15N NMR spectrum of ubiquitin—a protein containing several hundred interacting nuclear spins. Existing simulation algorithms for the spin system and the NMR experiment in question either require significant approximations or scale exponentially with the spin system size. We compare the proposed method to the Spinach package that uses heuristic restricted state space techniques to achieve polynomial complexity scaling. When the spin system topology is close to a linear chain (e.g., for the backbone of a protein), the tensor train representation is more compact and can be computed faster than the sparse representation using restricted state spaces.