Residential buildings consume a significant amount of Oman's electrical energy, and the air conditioning systems are the highest energy consumers in these buildings. Phase Change Material (PCM) is a new technology that stabilizes the indoor temperature and reduces energy consumption. The overall aim of this study is to evaluate the techno-economic feasibility of PCMs-embedded wall systems in residential buildings under four climates in Oman: hot-humid climate, moderate climate, hot-dry climate, and cold climate. A typical Omani villa was selected, and a simulation model was generated in DesignBuilder software and subsequently calibrated using actual electricity consumption readings. More than 160 variations of the thermophysical properties of the PCMs were explored for each climate. The thermophysical properties include melting temperature, latent heat, PCM's location, melting temperature range, density, heat capacity, and PCM's thickness. Enhancement techniques such as adding high conductive materials to the PCM, which include Ferrochrome slag, adding a layer of thermal insulation material, or using natural ventilation, were also explored to improve PCM's thermal and energy performance. The results showed that the optimal melting temperatures were 1 ºC above the thermostat setpoint for Muscat and Salalah and 2 ºC above the thermostat setpoint for Nizwa. Al Jabal Al Akhdar's optimal melting temperature is always 19 ºC. The optimal latent heat is 250 kJ/kg in Muscat and Salalah, 200 kJ/kg in Nizwa, and 400 kJ/kg in Al Jabal Al Akhdar. The best location for the PCM layer in hot climates was found on the inner side of the wall and the outer side for the cold climate. The study also found that the PCM's melting range, density, and heat capacity have no significant impact on reducing energy consumption in all climates. The optimal PCM layer thickness for all climates was 25 mm, which has doubled the annual energy consumption reduction compared to the 10 mm thick cases. After analyzing the PCM-Ferrochrome Slag Cement mixture plaster cases, it was found that all cases resulted in a lower reduction in energy consumption than the pure PCM, and the reduction of energy consumption negatively correlates with thermal conductivity. After that, the optimal properties found in this study were combined in one case for each climate. These cases have achieved a reduction in annual energy consumption of 3.28% for Muscat, 2% for Salalah, 3.65% for Nizwa, and 3.93% for Al Jabal Al Akhdar compared to the base case. The thermal performance analysis indicated that the PCM layer positively impacts the thermal performance between 1 pm and 1 am and negatively between 9 am and 11 pm for all climates. An economic analysis of the PCMs-embedded walls with the optimized properties was conducted, and it was found that they are economically infeasible. The study also found that the controlled natural ventilation slightly impacted energy performance and enhanced the PCM performance in the winter months only. Finally, a set of design guidelines for the PCMs-embedded wall systems for Oman were developed.