The incomplete consumption of sugar resulting from stuck wine fermentation is associated with important economic losses. One of the solutions to this serious problem consists of reinoculating the brew with a yeast starter culture that is both alcohol tolerant and a vigorous fructose fermenter. The present work aimed to select yeast strains capable of restarting stuck wine fermentations, and identify key parameters that bontribute to the efficiency of the strains. Commercial and non-commercial Saccharomyces wine strains were tested, as well as strains of the fermentative non-Saccharomyces species Zygosaccharomyces bailii and Torulaspora delbrueckii. Although the latter species were shown to be more resistant to a combination of ethanol- and acetic-acid-induced cell death, commercial Saccharomyces cerevisiae strains were the most efficient fructose consumers in medium simulating a stuck fermentation. Stationary-phase S. cerevisiae cells performed better than inocula prepared from exponentially growing cultures, which correlates with the higher resistance to ethanol of non-growing populations. Stationary-phase cells pre-adapted to ethanol did not improve fructose consumption rates; this was in contrast to exponential-phase cells that benefited from prior incubation in ethanol-containing medium. Notably, a correlation was observed between yeast fructose consumption capacity and glucose (or fructose) transport. Our results challenge the current belief that ethanol tolerance, expressed in terms of cell viability, is a reliable criterion for the selection of yeast strains to restart stuck fermentations. Instead, this capacity seems to be based on sugar transport and its resistance to ethanol. In an attempt to further improve cell viability the presence of high ethanol concentrations, hybrid strains of T. delbrueckii and S. cerevisiae were produced, and they showed high potential as restarter strains. The present work opens, perspectives for the application of innovative strategies in the wine-making industry.