We propose a method for measuring the temperature of strongly correlated phases of ultracold atom gases confined in spin-dependent optical lattices. In this technique, a small number of'impurity'atoms—trapped in a state that does not experience the lattice potential—are in thermal contact with atoms bound to the lattice. The impurity serves as a thermometer for the system because its temperature can be straightforwardly measured using time-of-flight expansion velocity. This technique may be useful for resolving many open questions regarding thermalization in these isolated systems. We discuss the theory behind this method and demonstrate proof-of-principle experiments, including the first realization of a three-dimensional (3D) spin-dependent lattice in the strongly correlated regime.