In pursuit of sustainable development, worldwide adoption of hydrogen fuel cell vehicles (HFCVs) is growing to cut carbon emissions in the transportation sector. The construction of hydrogen refueling stations (HRSs) is the key to popularizing HFCVs. The popularity of HRSs is hindered by cost, site selection, and user expectations. Selecting mature gas stations with large passenger flow to expand HRSs can improve the accuracy of the hydrogen refueling network. Reducing the range anxiety of HFCV users to improve the path coverage of HFCVs is a favorable way to expand the hydrogen vehicle industry chain. Therefore, this study proposes a bi-level programming model, which considers hydrogen source (HS), hydrogen delivery mode (HDM), initial remaining range, range anxiety, and other factors. The upper-level model is designed to optimize economic costs, including the total chain cost of the HRS. The lower level aims to optimize the range anxiety of HFCV users and more accurately reflect their autonomy by controlling the maximum remaining range of the vehicle. Finally, the expressway in the Liaoning Province of China is taken as an example to verify that the optimization model had the advantages of low hydrogen cost and minimal range anxiety. The cost analysis of several HSs and HDMs was discussed from the perspective of the best site selected, and it was found that the Anshan HS using coal to produce hydrogen and the long tube trailer can provide lower hydrogen cost for the HRS. This method is generalizable to other regions or all types of HFCVs.