We demonstrate spin gradient thermometry, a new general method of measuring the temperature of ultracold atoms in optical lattices. We realize a mixture of spins separated by a magnetic field gradient. Measurement of the width of the transition layer between the two spin domains serves as a new method of thermometry which is observed to work over a broad range of lattice depths and temperatures, including in the Mott insulator regime. We demonstrate the thermometry using ultracold rubidium atoms, and suggest that interesting spin physics can be realized in this system. The lowest measured temperature is 1 nK, indicating that the system has reached the quantum regime, where insulating shells are separated by superfluid layers.