Natural gas sweetening is required to remove the acid gas CO2 to meet gas grid specifications. Membrane technology has a great potential in this application compared to the state-of-the-art amine absorption technology. Carbon membranes are of particular interest due to their high CO2/CH4 selectivity of over 100. In order to document the advantages of carbon membranes for natural gas (NG) sweetening, HYSYS simulation and cost evaluation were conducted in this work. A two-stage carbon membrane process with recycling in the second stage was found to be technically feasible to achieve >98% CH4 with <2% CH4 loss. The specific natural gas processing cost of 1.122 × 10−2 $/m3 sweet NG was estimated at a feed pressure of 90 bar, which was significantly dependent on the capital-related cost. Future work on improving carbon membrane performance is required to increase the competitiveness of carbon membranes for natural gas sweetening.