The residue after sieving (“dust”) from the willow gentian underground parts is an unexploited herbal tea by-product, although it contains valuable bioactive compounds. Cyclodextrins as efficient green co-solvents, cage molecules, and multifunctional excipients could improve the extraction and contribute to the added value of the resulting extracts. The objective of this study was to determine the optimal conditions for the extraction of gentiopicroside, isogentisin, and total phenolics (TPC) from willow gentian “dust” using ultrasound-assisted water extraction coupled with hydroxypropyl-β-cyclodextrin (HPβCD). The influence of extraction temperature (X1: 20–80 °C), time (X2: 20–50 min), and HPβCD concentration (X3: 2–4% w/v) was analyzed employing the response surface methodology (RSM). The optimal extraction conditions for simultaneously maximizing the extraction yield of all monitored responses were X1: 74.89 °C, X2: 32.57 min, and X3: 3.01% w/v. The experimentally obtained response values under these conditions (46.96 mg/g DW for gentiopicroside, 0.51 mg/g DW for isogentisin, and 12.99 mg GAE/g DW for TPC) were in close agreement with those predicted, thus confirming the suitability and good predictive accuracy of the developed RSM models. Overall, the developed extraction system could be an applicable alternative strategy to improve the extraction of bioactive compounds from the underutilized “dust” of willow gentian underground parts.