Identification of novel tumor-associated antigens (TAA) capable of eliciting T-cell responses has renewed interest in the development of anti-tumor vaccines. The insertion of genes encoding specific TAA into a vaccinia virus (rVV) is one approach to vaccination since large amounts of foreign DNA can be stably integrated into the poxvirus genome. Recent reports have documented an increased therapeutic effectiveness of poxvirus-based vaccines when additional treatment with cytokines, such as interleukin-2 (IL-2) or interleukin-12 (IL-12) were used, but the combination of these cytokines as adjuvants for a rVV encoding TAA have not been previously reported. The combination of IL-2 and IL-12 at single regimen systemic doses was toxic and sometimes fatal, manifesting largely as segmental epithelial apoptosis of the large bowel. To explore the local delivery of both cytokines to the site of vaccination, the genes encoding IL-2 and IL-12 were inserted into vaccinia virus along with a model tumor antigen gene. This construct contained five heterologous genes: LacZ (the model antigen), gpt (reporter gene), IL-2, and the two IL-12 subunit genes (p35 and p40). Treatment with this recombinant virus resulted in a reduced number of pulmonary metastases, improved survival, and minimal toxicity in a murine tumor model. The use of vaccinia virus for the insertion of other heterologous gene combinations may provide a powerful and less toxic approach for novel vaccination strategies in the treatment and prevention of cancer.