De club werd opgericht in 1944 als USM Bône. Na de Algerijnse onafhankelijkheid van Frankrijk werd de stadsnaam gewijzigd in Annaba en dus ook de voetbalclub werd zo USM Annaba. In 1964 werd de club landskampioen. In 1969 werd de naam gewijzigd in Hamra Annaba omdat de overheid de vele Fransklinkende namen van voetbalclubs wilde wijzigen in meer Arabisch klinkende namen. In 1970 degradeerde de club voor het eerst uit de hoogste klasse. Na één jaar keerde de club terug en won in 1972 de beker. In 1976 volgde opnieuw een degradatie. De club slaagde er niet meer in terug te keren naar het hoogste niveau.
