The problem of retrofit design of refinery hydrogen networks is addressed in this work, using the mathematical superstructure optimization. The superstructure of retrofit hydrogen network design contains hydrogen using, producing, and purifying units; along with compressors to facilitate hydrogen distribution. The developed mathematical model is formulated as a mixed integer nonlinear programming model (MINLP), with the objective being minimum total annual cost. The nonlinearity in the model is because of the bilinear, posynomia, and linear fractional terms. A new heuristic method is presented which helps in assigning suction and discharge pressures for the newly retrofitted compressor. With such an assignment, the nonlinearity in the model is now only confined to bilinear terms. This bilinear MINLP model is solved to global optimality using the proposed global optimization algorithm. Tests on some literature examples show that the proposed algorithm can reach global solutions faster than some commercial MINLP global solvers.