Le premier match de l’équipe d'Algérie de football fut joué contre la Tunisie, en Tunisie, le 1er juin 1957. Cette Algérie n’est pas indépendante lors du match, mais elle s’est auto proclamée indépendante, et ce match est dans la continuité de la phase de décolonisation qui a cours. L’Algérie remporte ce match sur le score de 2 buts à 1. Avant l'indépendance du pays en 1962, des joueurs d'origine algérienne, tels Rachid Mekloufi, Abdelaziz Ben Tifour, ou encore Mohammed Zakraoui premier sélectionneur de l'équipe, ont joué pour l'équipe de France. Mahi Khennane a d'ailleurs joué d'abord pour la France puis pour l'Algérie[2]. En avril 1958, création, par Mohamed Boumezrag, de l'équipe clandestine du FLN[3], en exil à Tunis, par la désertion de joueurs algériens basés en France[4],[5]. La Fédération algérienne de football est fondée en 1962. Elle est affiliée à la FIFA depuis 1963 et membre de la CAF depuis 1964. L’Algérie, pour sa première participation à une compétition internationale, à savoir la CAN 1968. Elle repart de la CAN 1968 avec deux défaites contre l’Éthiopie (1-3, but de Boualem Amirouche) et contre la Côte d’Ivoire (0-3) et une victoire 4-0 sur l’Ouganda (triplé de Hassen Lalmas et but de Mokhtar Khalem). Elle participe pour la première fois aux qualifications de la Coupe du Monde en 1970.
Le 17 août 1973, en Libye, l’Algérie enregistra sa plus large victoire de son histoire contre le Yémen du Sud, sur le score de 15 buts à 1. Mais, le 21 avril 1976, à Cottbus, en RDA, l’Algérie enregistra sa plus large défaite contre la RDA sur le score de 5 but à 0. De 1970 à 1978 inclus, l’Algérie ne se qualifia pour aucune compétition internationale. Durant cette période, l’Algérie remporte les Jeux Méditerranéens en 1975 et les Jeux panafricains en 1978.
