Algeria caused one of the great World Cup upsets on the first day of the tournament with a 2–1 victory over reigning European ChampionsWest Germany. In the final match in the group between West Germany and Austria, with Algeria having already played their final group game the day before, the European teams knew that a West German win by 1 or 2 goals would qualify them both, while a larger German victory would qualify Algeria over Austria, and a draw or an Austrian win would eliminate the Germans. After 10 minutes of all-out attack, West Germany scored through a goal by Horst Hrubesch. After the goal was scored, the two teams kicked the ball around aimlessly for the rest of the match. Chants of "Fuera, fuera" ("Out, out") were screamed by the Spanish crowd, while angry Algerian supporters waved banknotes at the players. This performance was widely deplored, even by the German and Austrian fans. One German fan was so upset by his team's display that he burned his German flag in disgust. Algeria protested to FIFA, who ruled that the result be allowed to stand; FIFA introduced a revised qualification system at subsequent World Cups in which the final two games in each group were played simultaneously.
In the final against Nigeria, in front of 105,302 fans in the same stadium, Cherif Oudjani, in the 38th minute, enabled Algeria to win the African Nations Cup for the first time. Djamel Menad was crowned top scorer of the competition with four goals.
Algeria fans at a friendly vs. Republic of Ireland in Dublin.
On 11 October 2008, Algeria returned to the top 20 African teams by finishing first in their group ahead of Senegal, Gambia, and Liberia for the second round on the combined 2010 World Cup and 2010 African Cup of Nations qualifications. In the third and final round of the qualifiers, Algeria was joined by Zambia, Rwanda, and Egypt. In July 2009, Algeria made their return amongst the world's top fifty after a 3–1 win against the double African champions Egypt and a 2–0 away win against Zambia. Beating Zambia in Blida 1–0 followed by a 3–1 win against Rwanda, Algeria ensured that the qualification for the World Cup would go down to the wire with a final encounter against Egypt in Cairo, where nothing less than a loss by three goals would stop the Fennecs from going to South Africa. Prior to the game the Algerian team bus was attacked, leaving several team members injured. This led to a diplomatic row between the two countries. Algeria lost the game 2–0. Algeria won the resulting play off in Sudan 1–0. Algeria moved to the 29th position in FIFA ranking – one place behind Egypt in the October 2009 ranking. In November 2009, they beat fierce rivals Egypt in a playoff 2010 World Cup in South Africa and moved to the highest FIFA ranking ever reached by Algeria (26) in December 2009.
The team put on a mixed performance in the tournament. Being drawn in Group A, with Angola, Malawi and Mali, Algeria started poorly by losing 3–0 to group outsiders Malawi. However, they improved in the following game against Mali, beating them 1–0 thanks to a Rafik Halliche header. In the last match, they drew 0–0 with Angola, which sent them to the second round, finishing with the same amount of points as Mali, but with a superior head-to-head record. Playing in Cabinda, Algeria faced Côte d'Ivoire in the quarterfinals, who were considered heavy favourites to qualify. But they got a historic win. After trailing 1–0, Karim Matmour equalized, but Keita gave the Ivorians the lead in the 89th minute, a goal which seemed sure to seal their victory. However, the Algerians equalized with Madjid Bougherra just 2 minutes later in added time, and Hameur Bouazza gave the Fennecs the lead in extra time. Algeria faced Egypt in the semi finals, Egypt, in their first meeting since the World Cup qualification play-off. In a controversial match, Egypt won 4–0 which was the biggest defeat in the history of the teams' meetings. Algeria lost 1–0 to Nigeria in the third place game and finished fourth in the competition.
Algeria was drawn in Group C with England, USA, Slovenia. In their first game they lost to Slovenia 0–1. The match was scoreless until Slovenia's captain Robert Koren scored in the 79th minute after Abdelkader Ghezzal was sent off for his second bookable offence. In their second group game, Algeria drew with England leading to mass celebration throughout the world's Algerian communities. The Fennecs lost their final group game to the United States 1–0 thanks to a Landon Donovan winner in second-half injury time.