Spain need to overcome Norway to make the short trip to neighbouring Portugal, while the other four ties saw Latvia pitted against Turkey, Scotland drawn to play the Netherlands, Croatia paired with Slovenia and Russia drawn against Wales.
The ties will be played over two legs on November 15-16 and November 18-19.
The 10 teams finished as group runners-up in the qualifying competition that ended on Saturday.
Spain, third in the FIFA world rankings and the highest ranked nation in the draw, lost 1-0 to Norway in the finals of Euro 2000.
But the draw dismayed Norwegian coach Nils Johan Semb.
"This will be extremely challenging," he told Norwegian TV2. "We will have to work extremely hard. But nothing is impossible."
Semb had said before the draw that the Netherlands were the team he feared most in the playoffs with Spain second. Norway beat Spain 1-0 in their last match, at Euro 2000, with a goal by forward Steffen Iversen.
"That was some years ago," Semb said, declining to name the players he feared most in the Spanish side.
"The team is full of class players," he said.
Spain centre back Ivan Helguera told Spanish state radio that Norway would be tough to beat.
"They close up well and they have a lot of height up front," he said. "There were more difficult teams in the draw, though, so it's fine."
ADVOCAAT BACK
The Dutch were drawn to play Scotland, meaning a return to Scotland for Dutch coach Dick Advocaat, the former Rangers manager.
The two countries have a long rivalry dating back to 1929, but Scotland have not beaten the Dutch in six meetings since 1982, scoring only once in that time.
"It is a favourable draw, with the extra advantage of starting away," Advocaat said.
"I know most of their players, half play in the (English) Premier League and the rest in the Scottish Premier League. They are a hard-working team that plays with enthusiasm, for a home crowd that creates an enormous atmosphere."
"It is clear that we are favourites. I am pleased that we won't meet Turkey because they seemed the toughest opponent"
"For me personally it is a pleasure to be back in the country where I worked for four and a half years."
Scotland's German boss Berti Vogts told Sky Sports News: "We are the underdogs, the Netherlands are the big favourites. But we have to play two matches, and we know we played well against Germany (in qualifying), and they were also big favourites.
"We will need a lot of luck. Maybe the Netherlands will already be looking towards Portugal but they will have to fight against us."
Wales, seeking to reach a major finals for the first time since the 1958 World Cup, were drawn against Russia but Welsh boss Mark Hughes was optimistic.
Hughes told Sky Sports: "It's a tough draw but we knew whoever we were paired with it would be a difficult tie.
"We have avoided some of the more important footballing nations so I'm reasonably happy with the draw."
Vyacheslav Koloskov, head of Russia's football federation, was equally optimistic.
"Being drawn against Wales has given us a great deal of optimism," he said. "I think this is the best choice for us."
Latvian coach Aleksandrs Starkovs was downbeat after his side were paired with Turkey.
"We'll try our best, but it will be hard," Starkovs told Reuters. "They are definitely stronger than Sweden at the moment."
GREATEST ACHIEVEMENT
Latvia surprisingly reached the playoffs after beating Group Four winners Sweden 1-0 in Stockholm on Saturday, sending the small nation through at the expense of Poland in what local media hailed as Latvia's greatest football achievement.
"We are certainly happy that we have drawn a team that is behind us in football terms. We were the victims of a road accident on Saturday and we don't want to repeat that," Turkey team manager Can Cobanoglu was quoted as saying by Anatolian news agency.
Croatia, meanwhile, welcomed their draw against neighbouring Slovenia.
"We have high respect for what Slovenian team has achieved in the last several years, but we believe it is an opponent we can beat to qualify for Euro 2004," Croatia FA secretary-general Zorislav Srebric told Reuters.
Slovenia participated in Euro 2000 which Croatia did not, and both teams took part in last year's World Cup.
"I'm not satisfied with the draw. It's a match between neighbours and these are always tense and never easy," said Slovenia captain Miran Pavlin.
More from rediff