NaTiO2 has been predicted to have a variety of unusual magnetic states, depending sensitively on the details of the crystal structure and interaction strength between the magnetic Ti3+ ions. The material is particularly interesting because it also has potential battery applications. However, there have been remarkably few studies carried out on this system. Our collaborators have synthesized high quality NaTiO2, which exhibits transitions, assumed to be structural, at temperatures nearly 50 K higher than previously studied samples. We propose to carry out muon spin relaxation measurements to characterize the low temperature magnetic state of this system. The results will be correlated with parallel studies via neutron scattering of the crystal structure and magnetism.