Liquefied natural gas (LNG) is a clean burning fossil fuel, which offers an energy density comparable to petrol and diesel fuels. LNG production has grown five-fold in the last 25 years. Although there are a few dominant processes for land-based liquefaction plants, there is much interest in the production of LNG off-shore, particularly “Floating LNG” or FLNG. One option for FLNG is gas phase refrigeration cycles, which are very flexible and inherently safer than condensing refrigeration processes. A shaftwork targeting method has recently been developed for multi-stage gas-phase refrigeration systems (Shah and Hoadley, 2007). In this chapter, a study has been carried out to optimize these systems for multiple objectives, by varying the operating parameters such as the minimum temperature driving force (ΔTmin) and pressure ratio. An interesting aspect of this study is the use of a superstructure model for the process simulation in order to allow for different numbers of refrigeration stages (from 2 to 7 stages). The two objective functions considered in the present optimization study are the capital cost and the energy requirement. A Non-dominated Sorting Genetic Algorithm (NSGA-II) is used to generate the Pareto-optimal front, and an extended range of process parameters including the number of refrigeration stages is tested. The multi-objective optimization results are presented and discussed for two cases: cooling of a nitrogen stream using a nitrogen gas refrigerant, and the dual nitrogen/natural gas refrigerant process for LNG.