In this study, we investigated the connections among teacher-student relationships (TSRs), intrinsic motivation, self-efficacy, and non-routine problem solving (NPS) in mathematics with a moderated mediation model. A sample of 3,101 Chinese ninth-graders (1,654 urban students and 1,447 rural students) participated in a large-scale survey. The results showed that intrinsic motivation and self-efficacy mediated the relation between TSRs and NPS, respectively, controlling for SES and gender. Moreover, the positive path coefficients from TSRs to self-efficacy, as well as from both intrinsic motivation and self-efficacy to NPS for rural students were significantly larger than those for urban students. The findings suggest that TSRs support students' development in solving non-routine problems by boosting their intrinsic motivation and self-efficacy, especially for rural students. These findings extend the literature and provide some implications for educators and instructors.