Algeria caused one of the great World Cup upsets on the first day of the tournament with a 2–1 victory over the reigning European champions, West Germany. In the final match in the group between West Germany, Austria and Chile, 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. 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.
Madjer is considered one of the best football players in the history of Algeria.
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 the semi-final, 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. Algeria exited the championship as one of two teams, along with Honduras, to fail to score a goal.
After the World cup, bad results were growing and growing with no wins. During that period, Algeria failed to qualify for the 2012 Africa Cup of Nations which resulted their manager, Rabah Saâdane to be replaced with their new manager Abdelhak Benchikha. Their new manager brought new faces to the squad to bolster their offense but they still finished last in their group. After Algeria's 4–0 loss to Morocco, their manager resigned.
Algeria arrived to the 2013 Africa Cup of Nations with confidence and power but kicked off with a 1–0 loss to Tunisia following a 2–0 defeat to Togo which meant they couldn't advance to the next phase of the tournament. It was considered a shock as Algeria was considered as a favourite to win the competition. Algeria ended their campaign with a 2–2 draw with Ivory Coast.
After having a disappointing campaign in the 2013 Africa Cup of Nations, it was speculated that Halilhodžić was going to be sacked but the Algerian FA decided to stick with him. After confirming their manager's stay, Algeria continued the World cup qualifying camapign which they had started positively with one win and one loss. Algeria continued its campaign winning 3–1 versus Benin at home and beating them again 3–1 away of their stadium. They continued by winning versus Rwanda 1–0 away from their stadium, and that's how they guaranteed that they won the group. Their last game didn't mean anything but Algeria still won 1–0 versus Mali national football team at home and ended up finishing at the top of their group. After topping group H, Algeria was drawn with Burkina Faso as their final opponent. The 1st leg was held in Burkina, and the second was in Algeria. The first leg ended in 3–2 loss to Burkina Faso and it outraged some Algerian fans as Burkina was awarded a false penalty. The second leg was a harsh game but Algeria managed to scrap a controversial 1–0 victory to advance to the 2014 FIFA World Cup.
Algeria has been drawn in Group H with Belgium, Russia and South Korea. In their opening game, Feghouli scored Algeria's first World Cup goal for 28 years. In their second game against South Korea, Brahimi scored the fourth goal against the opposition to set a record of being the first African team to score four or more goals in a single match in the World Cup. On 26 June, Algeria played Russia for second place in Group H, Russia scored the opening goal but Slimani became a hero by scoring the equalizer to carry Algeria to the second round of the World Cup for the very first time.