A mechanism is identified whereby dark matter (DM) in protostellar halos alters the current theoretical framework for the formation of the first stars. Heat from the annihilation of the lightest supersymmetric DM particles is shown to overwhelm any cooling mechanism, consequently impeding the star formation process and possibly leading to a new stellar phase. A "dark star" may result: a giant (>~ 1 AU) hydrogen-helium star powered by DM annihilation instead of nuclear fusion, and detectable via annihilation products (gamma-rays, neutrinos, antimatter).