Purpose Metastatic breast cancer (MBC) is incurable; its treatment is palliative. We investigated whether the presence of circulating tumor cells (CTCs) predicts treatment efficacy, progression-free survival (PFS), and overall survival (OS) in patients with newly diagnosed MBC who were about to start first-line therapy. Patients and Methods One hundred seventy-seven patients with measurable MBC were enrolled onto a prospective study. Eighty-three of the 177 patients were entering first-line treatment, and these patients are the focus of this analysis. CTCs from 7.5 mL of whole blood drawn before treatment initiation (baseline) and monthly thereafter for up to 6 months were isolated and enumerated using immunomagnetics. Results The mean (± standard deviation) follow-up time was 11.1 ± 4.4 months (median, 12.2 months). Forty-three patients (52%) had ≥ five CTCs at baseline. The median PFS was 7.2 months (95% CI, 4.9 to 9.4 months), and the median OS was more than 18 months. Patients with ≥ five CTCs at baseline and at first follow-up (4 weeks) had a worse prognosis than patients with less than five CTCs (baseline: median PFS, 4.9 v 9.5 months, respectively; log-rank, P = .0014; median OS, 14.2 v > 18 months, respectively; log-rank, P = .0048; first follow-up: median PFS, 2.1 v 8.9 months, respectively; log-rank, P = .0070; median OS, 11.1 v > 18 months, respectively; log-rank, P = .0029). CTCs before and after the initiation of therapy were strong, independent prognostic factors. Conclusion Detection of CTCs before initiation of first-line therapy in patients with MBC is highly predictive of PFS and OS. This technology can aid in appropriate patient stratification and design of tailored treatments.