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 spores of anaerobic bacteria in combination with agents which interact with microtubules can cause the destruction of both the vascular and avascular compartments of tumors. Two classes of microtubule inhibitors were found to exert markedly different effects. Some agents that inhibited microtubule synthesis, such as vinorelbine, caused rapid, massive hemorrhagic necrosis when used in combination with spores. In contrast, agents that stabilized microtubules, such as the taxane docetaxel, resulted in slow tumor regressions that killed most neoplastic cells. Remaining cells in the poorly perfused regions of tumors could be eradicated by sponzlated bacteria. 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 spores could germinate. A single intravenous injection of spores plus selected microtubule-interacting agents was able to cause regressions of several tumors in the absence of excessive toxicity.