The first-order metal-insulator phase transition in VO2 is characterized by an ultrafast several-orders-of-magnitude change in electrical conductivity and optical transmittance, which makes this material an attractive candidate for the fabrication of optical limiting elements, thermochromic coatings, and Mott field-effect transistors. Here, we demonstrate that the phase-transition temperature and hysteresis can be tuned by scaling VO2 to nanoscale dimensions. A simple hydrothermal protocol yields anisotropic freestanding single-crystalline VO2 nanostructures with a phase-transition temperature depressed to as low as 32 degrees C from 67 degrees C in the bulk. The observations here point to the importance of carefully controlling the stochiometry and dimensions of VO2 nanostructures to tune the phase transition in this system.