Wastewater streams from fruit processing (e.g., olives) are usually rich in phenolic compounds, such as tyrosol, hydroxytyrosol and oleuropein. Even though phenolic compounds are considered as pollutants due to their toxicity to many organisms, they possess a potential to serve as carbon and energy sources for microorganisms, and as substrates for biochemical conversion into high-value products. The present review had the aim to collect information available on the utilization of phenolic compounds and to identify underlying mechanisms to develop processes for an efficient valorization of wastewater streams, such as olive mill wastewater, using microalgae. Microalgae are of particular of interest, as they have been used in various waste utilization approaches to form multiple high-value products. Although research has already been done in the field of biodegradation of phenolic compounds using microalgae, a satisfying utilization approach has not been presented yet, as the mechanism of degradation of phenolic compounds remains unclear. In this review, reported degradation of phenolic compounds is presented and classified into: Mineralization, biotransformation and removal under dark or light condition. Details of single experiments are presented and relevant conclusions from outcomes have been made in order to develop future utilization approaches.