We report that administration of celecoxib, a specific cyclooxygenase-2 (COX-2) inhibitor, in combination with a dendritic cell-based cancer vaccine significantly augments vaccine efficacy in reducing primary tumor burden, preventing metastasis, and increasing survival. This combination treatment was tested in MMTV-PyV MT mice that develop spontaneous mammary gland tumors with metastasis to the lungs and bone marrow. Improved vaccine potency was associated with an increase in tumor-specific CTLs. Enhanced CTL activity was attributed to a significant decrease in levels of tumor-associated IDO, a negative regulator of T cell activity. We present data suggesting that inhibiting COX-2 activity in vivo regulates IDO expression within the tumor microenvironment; this is further corroborated in the MDA-MB-231 human breast cancer cell line. Thus, a novel mechanism of COX-2-induced immunosuppression via regulation of IDO has emerged that may have implications in designing future cancer vaccines.