Thermophoresis, or the directional motion of colloidal particles in liquids driven by a temperature gradient, is of both fundamental interest and practical use. In this work we explore the thermophoresis of colloids suspended in nematic liquid crystals (LCs). We observe that the motion of these colloids is fundamentally different from that in isotropic systems as a result of elastic distortions in the director fields caused by the colloidal inclusions. In the case of a sufficiently large local temperature and gradient, the elastic energy drives negative thermophoresis of immersed particles, which has a strongly nonlinear dependence on temperature. We develop a theory that incorporates elastic energy minimization into the traditional thermophoretic formulation and demonstrated a good agreement with experimental observations. We also examine the temperature dependence of the effective viscosity of the colloids and highlight the large magnitude of the Soret coefficient (|ST| > 5000), which results from the inherent enhancement in thermophoresis due to elastophoretic considerations and suppression of Brownian diffusion in LC media.