In this paper, the hot and cold utilities of a complex natural gas refinery containing multiple heat exchanger networks (HENs) were properly selected. Following using pinch analysis for designing the HENs of the natural gas refinery, this selection could be done by considering available utilities in the plant under consideration. The plant network was divided into the five heat exchanger networks for better and precise estimation of utility requirements in each smaller network. By comparing the type and temperature level of the utility required in each network, the best utility could be selected, in order to use as the heating and cooling media in the plant network with a considerable reduced operating cost of the system. The results show that in the new network design, there was about 38 and 100% reduction in cooling air and BFW respectively, but 45% increase in cooling water, as cold utilities and almost 64.4, 30.0, 90.9 and 100% reduction in HP steam, LP steam, hot flue gas and electric heater as hot utilities, respectively relative to the existing network.