In the first round, 42 teams were paired 2-by-2 and played knockout matches home-and-away.
Those teams are the 5 teams that qualified for the 2002 World Cup Finals (Cameroon, Nigeria, Senegal, South Africa and Tunisia) and the 4 highest-ranking teams in FIFA world rankings of 25 June 2003 (Congo DR, Ivory Coast, Egypt and Morocco).
Zimbabwe Zambia Algeria Ghana Burkina Faso Mali Kenya Angola Togo Libya Liberia Congo Malawi Uganda Madagascar Sudan Swaziland Guinea Rwanda Gabon Lesotho Benin Botswana Mozambique Ethiopia Mauritius Namibia Sierra Leone Gambia Burundi Cape Verde Eritrea Tanzania Chad Niger Central African Republic Seychelles Mauritania Equatorial Guinea Guinea-Bissau Somalia São Tomé and Príncipe Mali won 4–1 on aggregate and advanced to the second round.
Cape Verde won 4–1 on aggregate and advanced to the second round.
3–3 on aggregate; Angola won on the away goals rule and advanced to the second round.