A cancer vaccine consisting of a recombinant fowlpox viral (FPV) vector encoding the human transcription factor and tumor-associated antigen (TAA) brachyury, and a triad of T-cell co-stimulatory molecules (TRICOM), which is comprised of the three human immune-enhancing co-stimulatory molecules B7-1, ICAM-1 and LFA-3, with potential immunostimulatory and antineoplastic activities. Upon subcutaneous administration occurring after the administration of a proprietary modified vaccinia Ankara developed by Bavarian Nordic-based prime vaccine (MVA-BN-brachyury), the booster vaccine FPV-brachyury vaccine potentiates a cytotoxic T-lymphocyte (CTL) response against brachyury-expressing tumor cells. The expression of brachyury, a member of the T-box family of transcription factors that is overexpressed in numerous cancer cell types, is correlated with increased epithelial-mesenchymal transition (EMT), cancer resistance, cancer progression and metastasis. TRICOM enhances antigen-specific T-cell activation.