Palm oil mill effluent (POME) is well known as agricultural wastewater that has a high potential as a medium for microalgal growth due to its high macro- and micronutrient content. The cyanobacterium Arthrospira platensis is considered as a species with a high C-phycocyanin (C-PC) content which is important for fine chemical and pharmaceutical applications. However, cultivation of A. platensis on POME to produce economically feasible amounts of C-PC has not been well explored. For this, environmental, nutritional, and cultivation modes (batch, semi-continuous) were varied to optimize C-PC productivity when cultivated at various POME concentrations. Arthrospira platensis was found to grow well on POME. Highest biomass and C-PC concentrations were found on 30–100% POME. Central composite rotatable design (CCRD) response surface methodology demonstrated that C-PC productivity was influenced by urea addition at the optimum salinity. The highest C-PC productivity was found on 100% POME during semi-continuous cultivation, while the addition of phosphorus and urea did not significantly improve C-PC productivity. By applying semi-continuous cultivation with 50% POME at the first stage and 100% POME at the second stage, a similarly high C-PC productivity (4.08 ± 1.3 mg L−1 day−1) was achieved as compared with (artificial) Zarrouk medium during batch cultivation. We conclude that, when using a two-stage semi-continuous cultivation process, A. platensis can produce economically feasible amounts of C-PC when cultivated on 100% POME.