We present a theory of the Seebeck effect in nanomagnets with dimensions smaller than the spin diffusion length, showing that the spin accumulation generated by a temperature gradient strongly affects the thermopower. We also identify a correction arising from the transverse temperature gradient induced by the anomalous Ettingshausen effect and an induced spin-heat accumulation gradient. The relevance of these effects for nanoscale magnets is illustrated by ab initio calculations on dilute magnetic alloys.