This study examined the anaerobic release of phosphorus (P) from two different Baltic Sea sediments (B and F), focusing on the impact of initial concentration of externally introduced waste-derived volatile fatty acids (VFA) as the carbon source, temperature, pH, and mixing conditions. The first batch bioreactor set was operated to demonstrate the effect of VFA on anaerobic P release at different concentrations (1000–10000 mg/L as COD) at 20 °C. A notable P release of up to 15.85 mg/L PO4–P was observed for Sediment B at an initial carbon concentration of 10000 mg COD/L. However, VFA consumption in the bioreactors was minimal or no subsequent. The second batch bioreactor set was carried out to investigate the effect of temperature (20 °C-35 °C), pH (5.5, 7.0 and 8.5) and mixing conditions on P release by introducing lower initial carbon concentration (1000 mg COD/L) considering the potential risk for VFA accumulation in the bioreactors. Maximum P releases of 4.4 mg/L and 3.5 mg/L were for Sediment B and Sediment F, respectively. Two-way ANOVA tests revealed that the operation time and pH and their interactions were statistically significant (p < 0.05) for both sediments while the effect of mixing was not statistically significant. Most of the sulfate was reduced during batch bioreactor operation and Desulfomicobiaceae became dominant among other sulfate-reducing bacteria (SRB) possibly shows the importance of SRB in terms of anaerobic P release. This study gives an insight into future implementations of phosphorus mining from eutrophic environment under anaerobic conditions.