Accurate estimation of the energy storage capacity of a cavern with a defined storage volume and type is the very first step in planning and engineering a Compressed Air Energy Storage (CAES) plant. The challenges in obtaining a reliable estimation arise in the complexity associated with the thermodynamics of the internal air compression and expansion processes and the coupled heat transfer with surroundings. This study developed the methodology for estimating the exergy storage capacity with a known cavern volume, as well as the cavern volume required for a defined exergy storage capacity with different operation and heat transfer conditions. The work started by developing the mathematical models of the thermodynamic responses of air in a cavern subject to cavern operation in isochoric uncompensated or isobaric compensated modes, and heat transfer conditions including isothermal, convective heat transfer (CHT) and adiabatic wall conditions. The simulated transient air pressure and temperature were verified with the operational data of the Huntorf CAES plant. The study of the Huntorf CAES cavern confirmed the importance of the heat transfer influence on the energy conversion performance. The increase of mass storage due to the reduced temperature variation leads to an enhanced total exergy storage of the cavern. According to our simulations, within the operating range of the Huntorf plant, 34.77% more exergy after the charging and 37.98% more exergy after throttling can be stored in the cavern with isothermal wall condition than those in the cavern with adiabatic wall condition. Also, the nearly isothermal behaviour and high operating pressure in the compensated isobaric cavern resulted in the high effectiveness of exergy storage per unit cavern volume. The required cavern volume of the assumed isobaric cavern operation can be reduced to only 35% of the current cavern volume at the Huntorf plant. Finally, cavern volumes for an operational gas storage facility were used to demonstrate the methodology in estimating the exergy storage capacity, which provided an initial assessment of the storage capacity in the UK.