Compressed air energy storage (CAES) systems represent a new technology for storing very large amount of energy. A peculiarity of the systems is that gas must be stored under a high pressure (p = 10–30 MPa). A lined rock cavern (LRC) in the form of a tunnel or shaft can be used within this pressure range. The rock mass surrounding the opening resists the internal pressure and the lining ensures gas tightness. The present paper investigates the key aspects of technical feasibility of shallow LRC tunnels or shafts under a wide range of geotechnical conditions. Results show that the safety with respect to uplift failure of the rock mass is a necessary but not a sufficient condition for assessing feasibility. The deformation of the rock mass should also be kept sufficiently small to preserve the integrity of the lining and, especially, its tightness. If the rock is not sufficiently stiff, buckling or fatigue failure of the steel lining becomes more decisive when evaluating the feasible operating air pressure. The design of the concrete plug that seals the compressed air stored in the container is another demanding task. Numerical analyses indicate that in most cases, the stability of the rock mass under the plug loading is not a decisive factor for plug design.