Compressed Air Energy Storage is a promising large-scale storage system in part because of its high power rating during discharge. But it is not the cleanest way of storing energy due to the necessity of an external heat source (typically the combustion of natural gas) to heat the air at the turbine inlet. This problem can be overcome with Thermal Energy Storage by storing the thermal energy of air at the compressor exhaust in order to be used for heating air before turbine. In this study, a numerical transient heat transfer model of Thermal Energy Storage is developed and the performance of Thermal Energy Storage is investigated based on heat storage capacity, required time to store unit amount of energy and air temperature profiles at the outlet of Thermal Energy Storage during discharge for the system. High heat storage per volume is necessary for more compact systems. Required time to store unit amount of energy is desired to be short for a fixed volume Thermal Energy Storage in order to maintain continuous operation; on the other hand, air at the outlet (turbine inlet) should be at a high temperature for the longest time possible to supply hot air to turbine. In order to investigate the effects of operating parameters, different volumes of Thermal Energy Storage tank filled with different storage mediums of various sizes are explored. Latent Heat and Sensible Heat Thermal Energy Storage systems are compared using magnesium chloride hexahydrate, paraffin, myristic acid and naphthalene as phase change materials and rock as sensible storage medium. Results show that Latent Heat Thermal Energy Storage gives a better performance than Sensible Heat Thermal Energy Storage. Among phase change materials, magnesium chloride hexahydrate provides the highest heat storage per volume. Required time to store unit amount of energy are comparable among the phase change materials. Magnesium chloride hexahydrate seems promising considering the discharge temperature profile at the Thermal Energy Storage outlet. Capsule size should be kept as small as possible which can be challenging in terms of manufacturing.