Cloud Point Extraction (CPE) technique was used to recover phenolic compounds from wine sludge wastes using lecithin as a surfactant. Lecithin is a safe natural product with no toxicity and, therefore, no separation of recovered phenolic substances from the surfactant system is required to use them in food systems. A progressive optimization sequence involving multiple recovery stages (up to three), various surfactant concentrations (2, 5, 10, 15% w/v), different temperatures (35–55 °C) and pH values (2.5–5.0) was followed to optimize the CPE procedure. The efficiency of the CPE procedure after altering the above parameters was determined by the recovery of polyphenols after CPE procedure. According to the results, a surfactant concentration of 5%, the use of multiple CPE steps, a pH value of 3 and a temperature of 40 °C were the optimal conditions for the separation of phenolic compounds from wine sludge using lecithin as a surfactant. In addition, the antioxidant activity of the extracts was determined using various methods, namely DPPH•, Rancimat and Differential Scanning Calorimetry. The surfactant rich phases (which include the polyphenols extracted from the waste) showed high antioxidant activity.