Hydrogen is drawing increasing attention as a carbon-neutral energy carrier. The effects of climate change are increasing the pressure to establish a hydrogen energy infrastructure. To facilitate the transition to hydrogen energy, a large number of hydrogen refueling stations (HRS)s will need to be constructed throughout the entire transportation network. With a limited financial budget, constructing them simultaneously is not possible. However, it is economical to develop a systematic decision-making framework for determining construction priorities for HRSs. In this study, we propose p-median based mixed integer linear programming (MILP) models to establish location and construction priorities. The models aim to maximize the contribution impact that is represented by the sum of average distances between HRS and its allocated hydrogen vehicles. The metropolitan city of South Korea, Seoul, is used as a case study to illustrate the applicability of the proposed methodology.