Marine bioprospecting offers possibilities for sustainable innovation based on marine genetic resources. How to regulate the use of such marine genetic resources entails several challenges. The rationale for the introduction of legislation on access and benefit sharing (ABS) from the use of genetic resources is elaborated using Norway as a case. Similarities and differences from other initiatives are presented with Australia as the comparative case. Several lessons are transferable to the Norwegian situation, and may also be of high relevance to other countries introducing ABS legislation. In both Norway and Australia, there is an expressed need for an ABS system that can include a model that is based on access permissions rather than mere registration. There are difficulties involved in monitoring the genetic material from access to actual commercial product, and in distinguishing between bioprospecting for scientific and commercial use, which complicates a determination of when benefit sharing should be triggered. We suggest that the idea of benefit-sharing could be supported by the principle of cost-sharing.