The expected increase in global food demand, as a consequence of a rising and wealthier world population, and an awareness of the limits and drawbacks of modern agriculture, has resulted in a growing attention to the potential of the seas and oceans to produce more food. The capture production of presently exploited marine fish stocks and other species has more or less reached its maximum and can only be slightly improved by better management. This leaves four alternative options open to increase marine food production: (1) manipulating the entire food web structure via removal of high trophic level species to allow an increasing exploitation of low trophic level species, (2) harvesting so far unexploited stocks, such as various fish species from the mesopelagic zone of the ocean or the larger zooplankton species from polar regions, (3) low-trophic mariculture of seaweeds and herbivorous animals, and (4) restoration of impoverished coastal ecosystems or artificially increasing productivity by ecological engineering. In this paper, we discuss these four options and pay attention to missing scientific knowledge needed to assess their sustainability. To assess sustainability, it is a prerequisite to establish robust definitions and assessments of the biological carrying capacity of the systems, but it is also necessary to evaluate broader socio-economic and governance sustainability.