Palm oil mill effluent (POME) is the major source of environmental hazard in palm oil industry. Yet, due to its high nutrient content, POME may offer opportunities for the growth of algae as a source of value-added compounds such as sulfated extracellular polysaccharide (sEPS) while simultaneously removing valuable nutrients such as phosphate. The aim of this paper was to evaluate growth, total sEPS production, and nutrient removal by the diatom Phaeodactylum tricornutum grown on POME under a range of experimental conditions (temperature, salinity, supplementation of extra nutrients). Phaeodactylum tricornutum was found to grow well on a range of POME concentrations, with 30% POME as optimum concentration. Nitrate and urea addition enhanced both growth rate and final biomass, whereas phosphate significantly stimulated growth only at low temperature. Box-Behnken response surface methodology revealed that interactions between temperature and salinity, and between temperature and urea influenced sEPS production. The highest total sEPS (140 mg L−1) concentration was recorded at 25 °C, 2.6% salinity, and 100 mg L−1 urea addition. Our study shows that POME wastewater, supplemented with urea at relatively high temperatures, can be considered as a potential medium for P. tricornutum to replace commercial nutrients while producing high amounts of sEPS and removing almost 90% of phosphorous from the wastewater.