Wind energy is an important field of development for the island of Gotland, Sweden, especially since the island has set targets to generate 100% of its energy from renewable sources by 2025. Due to the variability of wind conditions, energy storage will be an important technology to facilitate the continued development of wind energy on Gotland and ensure a stable and secure supply of electricity. In this study, the feasibility of utilizing the Middle Cambrian Faludden sandstone reservoir on Gotland for Compressed Air Energy Storage (CAES) is assessed. Firstly, a characterization of the sandstone beneath Gotland is presented, which includes detailed maps of reservoir thickness and top reservoir structure. Analysis of this information shows that the properties of the Faludden sandstone and associated cap rock appear favorable for the application of CAES. Seven structural closures are identified below the eastern and southern parts of Gotland, which could potentially be utilized for CAES. Scoping estimates of the energy storage capacity and flow rate for these closures within the Faludden sandstone show that industrial scale CAES could be possible on Gotland.