Background: Patients with completely resected metastases from colorectal cancer (CRC) remain at high risk of recurrence and death despite adjuvant chemotherapy. Recently, survival of prostate cancer patients was enhanced by antigen-presenting cell therapy. We investigated whether administration of an antigen-presenting cell vaccine based on dendritic cells (DC) after metastasectomy would reduce the risk of recurrence and increase survival. Methods: Patients (n=74) with no evidence of disease after resection of CRC metastases and completion of their physician-determined peri-operative chemotherapy were randomized 1:1 to four immunizations with: DC modified with the PANVAC-VF poxvectors encoding CEA, MUC1, CD54, CD58, and CD80 or the PANVAC-VF poxvectors along with GM-CSF at the injection site. We report recurrence-free survival (RFS) at 2 years and overall survival (OS). CEA specific T cell responses were measured by ELISPOT. Data from a prospectively registered, comparable, contemporary control group of patients who had undergone metastasectomy for CRC were also available. Results: The arms of the study and contemporary controls were well balanced. The majority of the toxicities for the DC and PANVAC arms respectively were grade 1, 2 injection site reactions (63% versus 64%), low grade fevers (17% vs 31%), myalgia (11% vs 11%), and fatigue (26% vs 34%). The two year RFS was similar in all groups (50, 56 and 55% for the DC arm, the PANVAC arm and the contemporary control group, respectively). However, there was a trend for improved RFS among patients with CEA-specific T cell responses (log rank p = 0.10). At a median follow-up of 40 months, 2 of 37 patients treated with DC and 5 of 37 treated with PANVAC alone have died, with a combined survival rate exceeding that of the unvaccinated control patients. Conclusions: Patients vaccinated after metastasectomy experienced a longer survival relative to contemporary controls. A phase III study of OS comparing patients vaccinated after resection with the DC vaccine and observation is warranted.