To achieve the ever-stringent sustainable goals, this paper aims to synthesize a heat integrated hydrogen regeneration network (HIHRN) using a graph-theoretic-based sequential method. Firstly, the optimal and near-optimal structures for a hydrogen regeneration networks (HRN) are determined using P-graph model with consideration of both impurity and pressure constraints. These networks are then used as inputs in P-HENS software to generate a list of optimal and near-optimal heat exchanger network (HEN) structures. An eight source and sink problem is used to demonstrate the effectiveness of the proposed method. There are 199,677 feasible HIHRN structures identified, while the 6 near-optimal solutions which are within 0.05% tolerance of the optimal network cost (i.e., less than 33.04 M$/y) are presented together with the top four HEN designs that can offer comparable costs (∼115,500 $/y). In addition, the impacts of pressure swing adsorber (PSA) pressure drop consideration and minimum temperature difference on the optimal design are also presented.