In both stars and in the early universe, the production of deuterium is the first step on the way to producing heavier nuclei. If the strong force were slightly weaker, deuterium would not be stable, and many authors have noted that nuclesynthesis would be compromised so that helium production could not proceed through standard reaction chains. Motivated by the possibility that other regions of space-time could have different values for the fundamental constants, this paper considers stellar evolution in universes without stable deuterium and argues that such universes can remain habitable. Even in universes with no stellar nucleosynthesis, stars can form and will generate energy through gravitational contraction. We show that such stars can be sufficiently luminous and long-lived to support life. Stars with initial masses that exceed the Chandrasekhar mass cannot be supported by degeneracy pressure and explode at the end of their contraction phase. The resulting explosive nucleosynthesis can provide the universe with some heavy elements. We also explore the possibility that helium can be produced in stellar cores through a triple-nucleon reaction (roughly analogous to the triple-alpha reaction). Next we show that with even trace amounts of heavy elements --- produced through the triple-nucleon process or by explosive nucleosynthesis --- the CNO cycle can operate and allow stars to function. Finally, we consider Big Bang Nucleosynthesis without stable deuterium and find that only trace amounts of helium are produced, with even smaller abundances of other nuclei. With stars evolving through gravitational contraction, explosive nucleosynthesis, the triple-nucleon reaction, and the CNO cycle, universes with no stable deuterium are thus potentially habitable, contrary to many previous claims.