Background: Exercise represents a viable non-pharmacological intervention to help treating insomnia but the interaction mechanisms between sleep and physical activity still remain poorly understood. The aim of this study was to investigate the effect of a aerobic exercise training intervention on sleep and core temperature. Methods: Twenty-four adult women suffering from insomnia participated in this study. They were randomized into an exercise group and a control group. Aerobic exercise training consisted in moderate to vigorous aerobic exercise training for 12 weeks. Outcome measures included both subjective (Insomnia Severity Index, ISI) and objective (actigraphy recordings) sleep quality assessments, and core body temperature continuously recorded for a minimum 24 h. Results: The exercise group showed a decrease in ISI (p < 0.001) and in various objective sleep parameters. The core temperature batyphase value was lowered (p = 0.037) whereas its amplitude was larger (p = 0.002). We also found a tight correlation between the evolution of insomnia and the evolution of mean night-time core temperature and batyphase values. Conclusions: A moderate to vigorous aerobic exercise program appears to be an effective non-drug therapy for improving sleep in women with insomnia. In addition, exercise programs should aim to increase core body temperature during practice to induce sleep-promoting adaptations and rebound.