Preheating is often required to prevent hydrate formation during the pressure reduction process in a natural gas distribution network’s pressure reduction station. This paper examines an energy recovery method to avoid the cost and energy consumption of this preheating. The primary aim is to assess the techno-economic feasibility of an energy recovery system based on the Ranque–Hilsch vortex tube coupled to a heat exchanger for large-scale application to the gas grid. To this end, a techno-economic model of the entire energy recovery system was included in an optimisation procedure. The resulting design minimises the payback period (PP) when the system is applied to the pressure reduction stations belonging to a particular gas grid. The pressure reduction stations always operate at an outlet pressure above atmospheric pressure. However, available performance models for the Ranque–Hilsch vortex tube do not permit prediction at backpressure operation. Therefore, a novel empirical model of the device is proposed, and a cost function derived from several manufacturer quotations is introduced for the first time, to evaluate the price of the Ranque–Hilsch vortex tubes. Finally, a nearly complete set of pressure reduction stations belonging to the Italian natural gas grid was chosen as a case study using actual operating parameters collected by each station’s grid manager. The results indicate that the environmental temperature strongly affects the technical and economic feasibility of the proposed energy recovery system. In general, pressure reduction stations operating at an ambient temperature above 0 °C are economically desirable candidates. In addition, the higher the energy recovery system convenience, the higher the flow rate and pressure drop managed by the station. In the Italian case study, 95% of preheating costs could be eliminated with a PP of fewer than 20 years. A 40% preheating cost saving is still possible if the maximum PP is limited to 10 years, and a small but non-negligible 3% of preheating costs could be eliminated with a PP of fewer than 4.5 years.