The present study introduces a new treatment modality for comorbid insomnia and depression that combines cardiovascular exercise and elements of cognitive behavioral treatment: Exercise Based Cognitive Therapy (EBCT). While simultaneously performing moderate - high intensity cardiovascular exercise, participants were instructed to focus on problems, goals and negative automatic thoughts. The key principal of EBCT is the combination of focused problem solving with physical activity. This intervention targeted individuals in a common workplace who self identified as needing assistance with stress management. The intervention involved 12 sessions, increasing in cardiovascular intensity with each successive session. Study participants completed several psychological and sleep measures pre- and post-intervention. After three months, participants completed qualitative feedback of their overall experience. A total of 18 individuals participated in the intervention, all female, mean age 39.4 years (SD =9.04). On average, participants attended 5.00 (SD=3.74) sessions. Participants were predominantly Caucasian (72.2%), and a majority had a college education or beyond (55.5%). ANCOVAs were conducted to assess changes in the outcomes of interest. Tests of within-subjects effects demonstrated significant improvements in depression, insomnia, total sleep time, sleep latency, sleep efficiency, anxiety, perceived stress, automatic negative thoughts, and coping self-efficacy. Number of sessions attended was a significant covariant for the models for sleep latency, sleep efficiency, and coping self-efficacy. In contrast the number of sessions attended did not predict the magnitude of changes in anxiety and depression. Qualitative feedback had a 78.6% response rate; 100% of the respondents indicated the intervention was beneficial. This study presents the first investigation in which principles of psychotherapy were combined with physical exercise as a treatment approach to comorbid insomnia and depression. This new treatment modality was acceptable to participants, and demonstrated that a non-pharmacologic approach can have positive effects, simultaneously, on sleep, anxiety and depression. The ease with which the protocol was administered demonstrates that it may be attractive to patients and clinicians as an alternative to more formal psychotherapy or more informal general recommendations to increase physical activity.