Ultrasound-assisted extraction is widely recognized as an eco-friendly technique due to low solvent consumption and time extraction as well as enhanced extraction efficiency with respect to conventional methods. Nevertheless, it would be convenient to avoid the usually used organic solvents to reduce the environment pollution. In this regard, Deep Eutectic Solvents (DES) represent nowadays a green and sustainable alternative for the extraction of bioactive compounds from natural sources. In this study, an efficient extraction of stevioside and rebaudioside A from Stevia rebaudiana coupling ultrasound with DES was developed. A solvent screening was performed using the predictive approach COnductor-like Screening MOdel for Real Solvent (COSMO-RS). The effect of three independent variables, namely % of water, temperature, and sonication amplitude, were investigated by the response surface methodology (RSM). Comparing ultrasound-assisted extraction (UAE) with conventional extraction, it has been demonstrated that the amount of steviol glycosides through UAE is almost three times higher than that obtained by the conventional method. Possible physicochemical factors involved in the UAE mechanism were discussed.