In this paper, a novel liquefied air energy storage (LAES) system driven by wind energy and natural gas, integrated with a two-stage supercritical carbon dioxide cycle is proposed and investigated. Three different sensible thermal energy storage (TES) systems are considered in this study to store the heat produced in the compressions stage and use it later to improve the performance. The proposed system is analyzed in terms of energy, exergy, exergo-economic, and environmental impacts. A detailed economical and technical investigation is carried out to determine system hotspots, exergy destruction rates, and the performance of the system and subsystems. Finally, by considering ten design variables, the nondominated sorting genetic algorithm-II (NSGA-II) is employed to evaluate the optimal design solutions for double objective functions, including cost per unit of exergy and overall system exergy efficiency. Results indicate that for a 50 MW of discharging power, 80.75 MW of charging electricity and 1.22 kg/s of fuel are required. Additionally, the product cost per unit of exergy and the levelized costs are calculated as 32.02 $/GJ and 0.133 $/kWh, respectively. The results of the optimization study also show that for the optimal Pareto solution, the energy efficiency would be 52.2% while the exergy efficiency is 45.26%.