Cauliflower waste contains high amounts phenolic compounds, but conventional solvent extraction misses high amounts of nonextractable phenolics (NEP), which may contribute more to the valorization of these waste streams. In this study, the NEP content and composition of cauliflower waste were investigated. The ability of alkaline hydrolysis, sonication, and their combination to release NEP was assessed. Alkaline hydrolysis with sonication was found to extract the highest NEP content (7.3 ± 0.17 mg gallic acid equivalents (GAE)/g dry waste), which was higher than the extractable fraction. The highest yield was obtained after treatment of 2 M NaOH at 60 °C for 30 min of sonication. Quantification and identification were done using U(H)PLC-DAD and U(H)PLC-ESI-MS(E). Kaempferol and quercetin glucosides along with several phenolic acids were found. The results of the study show that there are higher amounts of valuable health-promoting compounds from cauliflower waste than what is currently described in the literature.