The short chain fatty acid (SCFA) butyrate is a product of colonic fermentation of dietary fibers. It is the main source of energy for normal colonocytes, but cannot be metabolized by most tumor cells. Butyrate also functions as a histone deacetylase (HDAC) inhibitor to control cell proliferation and apoptosis. In consequence, butyrate and its derived drugs are used in cancer therapy. Here we show that aggressive tumor cells that retain the capacity of metabolizing butyrate are positively selected in their microenvironment. In the mouse xenograft model, butyrate-preselected human colon cancer cells gave rise to subcutaneous tumors that grew faster and were more angiogenic than those derived from untreated cells. Similarly, butyrate-preselected cells demonstrated a significant increase in rates of homing to the lung after intravenous injection. Our data showed that butyrate regulates the expression of VEGF and its receptor KDR at the transcriptional level potentially through FoxM1, resulting in the generation of a functional VEGF:KDR autocrine growth loop. Cells selected by chronic exposure to butyrate express higher levels of MMP2, MMP9, α2 and α3 integrins, and lower levels of E-cadherin, a marker for epithelial to mesenchymal transition. The orthotopic model of colon cancer showed that cells preselected by butyrate are able to colonize the animals locally and at distant organs, whereas control cells can only generate a local tumor in the cecum. Together our data shows that a butyrate-rich microenvironment may select for tumor cells that are able to metabolize butyrate, which are also phenotypically more aggressive.