The geological storage of carbon dioxide (CO) offers notable potential, as part of larger carbon dioxide capture and storage (CCS) processes, to be a significant climate change mitigation technology. This paper challenges the argument often put forward that, due to the greater distances from centres of population, it will be 'easier' to garner public and stakeholder support for offshore CO storage than onshore. Based on the results of research interviews carried out with stakeholders and informed publics in Scotland, challenges for public and stakeholder acceptance of sub-seabed CO storage that may require further policy attention are identified. Whilst existing policy for sub-seabed CO storage is cognisant of the need for societal engagement, it may be the case that these regulations may need further reinforcement to ensure future developments are able to address social acceptability issues as fully as possible. The value of taking into account social as well as physical characteristics at the site selection phase, the need for mechanisms to take seriously stakeholder conceptions of uncertainty, and the importance of extending social engagement beyond risk communication are discussed.