Blockade of CTLA-4 by monoclonal antibodies (mAb) can mediate regression of tumors and increase the efficacy of tumor antigen specific vaccines. Blockade of CTLA-4 has also been shown to significantly increase the avidity of antigen-specific T cells after immunization with live recombinant viral vector based vaccine. Here, we demonstrate a biological synergy between CTLA-4 blockade and active vaccine therapy consisting of recombinant vaccinia and avipox viruses expressing carcinoembryonic antigen (CEA) and three T cell costimulatory molecules to enhance antitumor effects. However, this synergy was very much dependent on the temporal relationship of scheduling of the two agents. We evaluated the strategies in both a foreign antigen model using beta-galactosidase as immunogen, and in a "self" antigen model using CEA as immunogen. For antitumor activity the model used consisted of mice transgenic for human CEA and a murine carcinoma cell line transfected with CEA. The enhanced antitumor activity after vaccine and CTLA-4 blockade did not result in any signs of autoimmunity. These studies form a rational basis for the use of vector-based vaccines with anti-CTLA-4 and demonstrate that both enhancement of positive costimulatory signals and inhibition of negative costimulatory signals can be simultaneously exploited. These studies also underscore the importance of "drug" scheduling in vaccine combination therapies.