Seedlessness is one of the most desirable traits for table and raisin grapes. Stenospermocarpic cultivars are desirable because they have large berries with superior quality. Embryo rescue techniques have been widely used to get progeny seedling populations from crosses using seedless mother plants. Selection of the female parent, sampling time, and the growth medium are the most crucial to the success of this technique. This study investigated the effect of best sampling time and media composition on embryo rescue efficiency in a cold-hardy hybrid grape breeding program. We sampled ovules 5 to 9 weeks after flowering, and we tested four media compositions. The greatest percentages of embryo germination and normal seedlings were obtained when ovules were harvest at 8 weeks after flowering, indicating that it is suitable to harvest ovules at veraison, when the extraction of ovules is easier as a result of softer berry flesh. For the media composition experiment, all ovules were harvested at 8 weeks after flowering. Nitsch & Nitsch culture medium had very low germination, and the resulting seedlings performed the lowest compared with the other treatments. Lloyd & McCown Woody Plant Basal Medium (WPM) increased the number of embryos germinated significantly, and a number of normal seedlings and plantlets developed. Although there was no significant difference among the other three media containing WPM supplemented with different doses of plant regulators, the WPM Plus medium [with cytokinin (6-benzlaminopurine), indole-3-butyric acid, gibberellin, and casein hydrolysate] promoted the greatest percentage of established plants (46.98%). Therefore, the 8-weeks-after-flowering harvest time and the WPM Plus medium were selected for use in the embryo rescue protocol at the University of Minnesota grape breeding program.