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. Weakly Interacting Massive Particles, which may be their own antipartners, collect inside the first stars and annihilate to produce a heat source that can power the stars. A new stellar phase results, a Dark Star, powered by dark matter annihilation as long as there is dark matter fuel, with lifetimes from millions to billions of years. We find that the first stars are very bright (a million times solar) diffuse puffy objects during the DS phase, and grow to be very massive (500-1000 times as massive as the Sun). These results differ markedly from the standard picture in the absence of DM heating; hence DS should be observationally distinct. Once the dark matter fuel is exhausted, the DS becomes a heavy main sequence star; these stars eventually collapse to form massive black holes that may provide seeds for supermassive black holes observed at early times as well as in galaxies today.