Objective: Multiple trials have found telephone-administered cognitive behavioral therapy (T-CBT) to be effective for the treatment of depression. The aim of this study was to evaluate T-CBT for the treatment of depression among veterans served by community-based outpatient clinics (CBOCs) outside of major urban areas. Method: Eighty-five veterans meeting "Diagnostic and Statistical Manual of Mental Disorders" (4th ed.; American Psychiatric Association, 1994) criteria for major depressive disorder were randomized to receive 16 sessions of T-CBT over 20 weeks or treatment as usual through the CBOC. Veterans were assessed at baseline, 12 weeks, 20 weeks (posttreatment), and 6-month follow-up using the Hamilton Depression Rating Scale (Hamilton, 1960), the Patient Health Questionnaire-9 (Kroenke, Spitzer, & Williams, 2001), and a standardized psychiatric interview. Results: There were no significant Time x Treatment effects (ps greater than 0.20). Patients were compliant, with 38 (92.7%) completing at least 12 sessions, and 32 (78.0%) having no missed sessions whatsoever. Ratings of audiotaped sessions showed the therapists to be highly competent. Conclusions: This trial yielded negative results for an intervention that has been shown to be effective under other circumstances. We speculate that veterans served within the Veterans Affairs system are more refractory to treatment than other populations, and they may require a more rigorous intervention. Trial Registration: clinicaltrials.gov NCT00223652. (Contains 1 figure and 1 table.)