Global phosphorus reserves are under pressure of depletion in the near future due to increased consumption of primary phosphorus reservoirs and improper management of phosphorus. At the same time, a considerable portion of global marine water bodies has been suffering from eutrophication due to excessive nutrient loading. The marine environment can be considered as a valuable phosphorus source due to nutrient rich eutrophic seawater and sediment which could potentially serve as phosphorus mines in the near future. Hence, sustainable phosphorus recovery strategies should be adapted for marine systems to provide phosphorus for the growing market demand and simultaneously control eutrophication. In this review, possible sustainable strategies for phosphorus removal and recovery from marine environments are discussed in detail. Bio-based strategies relying on natural phosphorus uptake/release metabolism of living organisms are suggested as promising options that can provide both phosphorus removal and recovery from marine waters for achieving a sustainable marine ecosystem. Among them, the utilization of microorganisms seems promising to develop novel strategies. However, the research gap for the technical applicability of these strategies is still considerably big. Therefore, future research should focus on the technical development of the strategies through laboratory and/or field studies. Coupling phosphorus mining with other valorisation pathways (i.e., metal recovery, energy production) is also suggested to improve overall sustainability and economic viability. Environmental, economic and societal challenges should altogether be well addressed prior to real scale applications.