Solid tumors require vascularization for their growth. Bone marrow-derived endothelial progenitor cells participate in tumor angiogenesis. Here, we show that nicotine markedly accelerated growth of colon cancer cells inoculated subcutaneously in mice but had no effect on proliferation of carcinoma cells in vitro. We found that the tumor growth was associated with increased vascularization of the tumor and that bone marrow-derived cells contributed to the formation of the new blood vessels. Our findings show that nicotine promotes tumor growth, at least in part, by stimulating tumor-associated neovascularization.