Anthony Aguirre (UCSC), Peter Bodenheimer (UCSC), Katherine Freese(Univ Of Mich), Paolo Gondolo (Univ of Utah) We have proposed that the first phase of stellar evolution in the history of the Universe may be Dark Stars (DS), powered by dark matter heating rather than by nuclear fusion, and in this paper we examine the history of these DS. The power source is annihilation of Weakly Interacting Massive Particles (WIMPs) which are their own antiparticles. These WIMPs are the best motivated dark matter (DM) candidates and may be discovered by ongoing direct or indirect detection searches (e.g. FERMI /GLAST) or at the Large Hadron Collider at CERN. A new stellar phase results, powered by DM annihilation as long as there is DM fuel, from millions to billions of years.