Hydrogen passivation is an important method used to stabilize a specific graphene edge. Although several hydrogen-terminated graphene edges have been proposed in theory, a comprehensive exploration of highly stable hydrogen-terminated graphene edges is still absent. According to the bare graphene-edge databases, a series of hydrogen-terminated graphene edges have been proposed. The energy stability of hydrogen-terminated zigzag and armchair graphene edges is fully investigated. The six most stable hydrogen-terminated zigzag edges and six armchair edges of graphene are determined. Hydrogen passivation makes hydrogen-terminated graphene edges energetically more stable than bare graphene edges. The additional hydrogen atoms balance the dangling bonds of carbon atoms at edges by forming hydrogen-carbon covalent bonds. Hydrogen-terminated graphene edges with six-membered carbon rings have better global stability than those composed of non-hexagonal structural units. The effects of the experimental temperatures and hydrogen partial pressures on the stability of hydrogen-terminated graphene edges are fully investigated. Furthermore, hydrogen passivation can open the band gap of graphene effectively. These results provide a deep understanding of hydrogen-terminated graphene nanostructures.