We observe and study a special ground state of bosons with two spin states in an optical lattice: the spin-Mott insulator, a state that consists of repulsively bound pairs that is insulating for both spin and charge transport. Because of the pairing gap created by the interaction anisotropy, it can be prepared with low entropy and can serve as a starting point for adiabatic state preparation. We find that the stability of the spin-Mott state depends on the pairing energy, and observe two qualitatively different decay regimes, one of which exhibits protection by the gap.