Injecting CO2 into deep saline formations represents an important component of many greenhouse-gas-reduction strategies for the future. A number of authors have posed concern over the thousands of injection wells likely to be needed. However, a more important criterion than the number of wells is whether the total cost of storing the CO2 is market-bearable. Previous studies have sought to determine the number of injection wells required to achieve a specified storage target. Here an alternative methodology is presented whereby we specify a maximum allowable cost (MAC) per ton of CO2 stored, a priori, and determine the corresponding potential operational storage capacity. The methodology takes advantage of an analytical solution for pressure build-up during CO2 injection into a cylindrical saline formation, accounting for two-phase flow, brine evaporation, and salt precipitation around the injection well. The methodology is applied to 375 saline formations from the U.K. Continental Shelf. Parameter uncertainty is propagated using Monte Carlo simulation with 10 000 realizations for each formation. The results show that MAC affects both the magnitude and spatial distribution of potential operational storage capacity on a national scale. Different storage prospects can appear more or less attractive depending on the MAC scenario considered. It is also shown that, under high well-injection rate scenarios with relatively low cost, there is adequate operational storage capacity for the equivalent of 40 years of U.K. CO2 emissions.