Colorectal cancers are the third leading cause of cancer-associated deaths in the United States. Carcinoembryonic antigen (CEA) is a glycoprotein which is overexpressed in all adenocarcinomas of the colon and rectum and is extensively used as a serologic marker of colon cancer. Its presence in the normal fetal colon, as well as in gut crypts and healing intestinal mucosa of adults makes it a challenging immunologic target, as cytotoxic T lymphocytes (CTL) must overcome tolerance and be directed towards CEA-expressing cancer cells while sparing normal CEA-expressing cells. CAP1-6D, a unique 9-mer peptide of the CEA protein with a single amino acid mutation has been identified as a tumor specific antigen that can induce a stronger immune response than the wild type CEA peptide. Costimulatory signals, such as B7.1 are also critically important in the generation of an effective T cell response to any antigen. The cytokine GM-CSF is a useful vaccine adjuvant for its ability to increase antigen-presenting cells and enhance the antigen-specific anti-tumor response. Additionally, interferon-alpha as an adjuvant can enhance the expression of tumor antigens, such as CEA. This chapter describes the rationale for a clinical trial in which two virus-based CEA vaccines encoding the CAP1-6D peptide as well as costimulatory molecules (B7.1, ICAM-1, and LFA-3) were administered along with the vaccine adjuvants interferon-alpha and GM-CSF.