Current approaches for treating cancer are limited, in part, by the inability of drugs to affect the poorly vascularized regions of tumors. We have found that C. novyi-NT in combination with anti-microtubule agents can cause the destruction of both the vascular and avascular compartments of tumors. The two classes of microtubule inhibitors were found to exert markedly different effects. Some agents that inhibited microtubule synthesis, such as HTI-286 and vinorelbine, caused rapid, massive hemorrhagic necrosis when used in combination with C. novyi-NT. In contrast, agents that stabilized microtubules, such as the taxanes docetaxel and MAC-321, resulted in slow tumor regressions that killed most neoplastic cells. Remaining cells in the poorly perfused regions of tumors could be eradicated by C. novyi-NT. Mechanistic studies showed that the microtubule destabilizers, but not the microtubule stabilizers, radically reduced blood flow to tumors, thereby enlarging the hypoxic niche in which C. novyi-NT spores could germinate. A single intravenous injection of C. novyi-NT plus selected anti-microtubule agents was able to cause regressions of several human tumor xenografts in nude mice in the absence of excessive toxicity.