The 1998 world champions know that they will have their work cut out getting the better of Mikhail Fomenko's men, who are unbeaten in 11 games
The former midfield enforce was part of the team that lost 2-1 to Bulgaria at the Parc des Princes in November 1993, a result that ended Les Bleus' hopes of securing a place at the 1994 World Cup under the stewardship of Gerard Houllier.
Deschamps would go on to captain France to World Cup glory on home soil in 1998, and they have qualified for each of the three tournaments since then - including 2006, when they finished runners-up to Italy.
However, the 45-year-old trainer admits he is still haunted by their failure 20 years ago and is focused on ensuring this current France side suffer similar heartbreak.
"It may have been 20 years ago but it still sticks in my mind," Deschamps confessed. "I don't want to experience that again.
"We're playing two games in five days with no points at stake. Our goal is crystal clear - to qualify for the World Cup."
France travel to Kiev for the first leg on Friday, before the return encounter at the Stade de France on November 19.
Manchester United full-back Patrice Evra is included in the squad despite a recent media outburst in which he labelled World Cup winner Bixente Lizarazu and three other commentators as "tramps".
There are no other surprises, though, with Bayern Munich star Franck Ribery likely to be relied upon to provide the attacking impetus, after scoring four goals in his last three internationals.
France will start as favourites for the encounter but face a difficult task against a Ukraine side that are undefeated in 11 matches, with 10 of those under the guidance of Mikhail Fomenko, who took charge in December 2012.
Part of their success is down to a solid defence, with Ukraine racking up seven straight clean sheets.
Ukraine had to settle for a play-off spot in Group H after finishing runners-up to England and, like France in 1994, have been subject to past World Cup heartbreak.
Play-off defeats to Croatia, Germany and Greece stopp them reaching the World Cup in 1998, 2002 and 2010.
However, Fomenko is unperturbed by history as he looks to take his country to the World Cup for the first time since 2006.
"Only journalists and fans are speaking about those matches. My team try not to think about what happened before," he said.
Wingers Andriy Yarmolenko and Yevhen Konoplianka are Ukraine's primary attacking threats, with the former having scored four times in the group stages.