Virotherapy is an emerging strategy for the treatment of cancer that utilizes both replication-competent and genetically modified viruses to selectively kill tumor cells. We have previously shown that Coxsackievirus A21 (CVA21), a common-cold producing enterovirus, is an effective oncolytic agent against human melanoma, prostate, and breast cancer xenografts in vivo. CVA21 specifically targets and lytically infects susceptible cells expressing the CVA21 cellular receptors, intercellular adhesion molecule-1 (ICAM-1) and decay-accelerating factor (DAF). Herein, the efficacy of CVA21 administered in combination with doxorubicin hydrochloride as a new therapeutic regimen for cancer was investigated. Flow cytometric analysis demonstrated that the human breast, colorectal, and pancreatic cancer cell lines examined expressed moderate levels of surface ICAM-1 and DAF, whilst a normal breast cell line expressed only minimal levels. When CVA21 was combined with doxorubicin hydrochloride, synergistically enhanced cell death was observed when CVA21 was administered both simultaneously or 24 h prior to doxorubicin hydrochloride exposure. Doxorubicin hydrochloride had no effect on CVA21 replication. Through the use of an orthotopic (MDA-MB-231-luc) xenograft SCID mouse model of human breast cancer we showed that a single intravenous injection of CVA21 in combination with an intraperitoneal injection of doxorubicin hydrochloride resulted in significantly greater tumor reduction compared to either agent alone. Overall, these findings highlight the exciting potential of CVA21, administered in combination with doxorubicin hydrochloride, as a new therapeutic regimen for cancer.