La naissance d'un club de football à Chlef date bien avant l'année 1936 avec l'existence de l'équipe de l'époque, appelée «Seddikia». L'un de ses membres, Zerrouki M'hamed, sera parmi les fondateurs de l'ASO, dont l'un des objectifs était de contrecarrer les desseins d'un club colonial, le Groupement Sportif Orléansvillois, GSO. L'ASO débutera dans un championnat qui n'avait pas un caractère officiel dénommé «Coupe du Chélif». Parmi les joueurs de l'époque, nous citerons Chaïb Mohamed, Medjaher Abdelkader, Kenniche, Zerrouki Mohamed et Harchouche Abdelkader. En 1945, les dirigeants de l'ASO furent contraints de cesser toute activité, et ce n'est que le 13 juin 1947 que l'ASO fut agréée, s'engageant en compétition lors de la saison 1947-1948. Malgré de multiples contraintes, l'ASO termina au cours de cette saison en deuxième position, derrière l'Olympique d'Affreville (El-Khemis) en championnat de troisième division. L'ASO effectua la saison 1948-49 de la plus belle façon, arrachant le titre de la troisième division, accédant ainsi en seconde division. La saison suivante (1949-1950), l'ASO renouvela son exploit en s'adjugeant le titre de champion de la deuxième division. L'ASO fut éliminée de la coupe d'Algérie à Blida, par le Red Star sur le score de 3 buts à 2. Suite à l'appel du FLN, l'ASO, et tout comme les autres clubs musulmans cessa ses activités lors de la saison 1955-1956. Pour rappel, neuf joueurs de l'ASO sont tombés au champ d'honneur. A l'indépendance, l'ASO reprit ses activités. L'effectif de l'époque de l'ASO était composé de joueurs de talent tels Maîmoun, Djelly 1, Meddadi, Dif et Feknous. Après dix saisons en division d'honneur, l'ASO accéda en division régionale à l'issue de la saison 1971-72. Lors de la saison 1975-1976, l'équipe entraînée par feu Mazouza accéda en Nationale II, avant d'intégrer l'élite en 1982-83 sous la direction de Hamouni Abdellah. En 1992, l'équipe est qualifiée en finale de la coupe d'Algérie, qu'elle perd devant la JSK par la plus petite des marges au stade Zabana à Oran. En 2005, elle se qualifie une seconde fois en coupe d'Algérie, mais cette fois-ci, c'est une grande première dans l'histoire du club. En effet, au stade du 5 Juillet, l'ASO ramène le trophée à la grande joie de pas moins de 45.000 fans chélifiens. La population de Chlef a retrouvé une équipe performante lors de la première édition du championnat professionnel instaurée en Algérie, qu'elle a remporté haut la main à quatre journées de l'épilogue et devient ainsi champion d'Algérie. Il s'agit du premier titre de l'histoire du club et aussi le premier du championnat national professionnel.
