L'ENA fut fondée en 1926 par un militant communiste algérien, Abdelkader Hadj-Ali, sous l'impulsion de l'Internationale Communiste, désireuse de développer le travail communiste parmi les travailleurs maghrébins. Dès 1927, Messali Hadj rejoint l'organisation et en prend rapidement la direction.

Le programme de l'Étoile est défini la même année : abolition du code de l'indigénat, réforme agraire, libertés démocratiques et droit de vote universel, enseignement obligatoire en arabe, etc. Sur le plan politique, l'ENA défend l'indépendance de l'Algérie et la mise en place d'une assemblée constituante.

En 1928, a lieu la rupture entre l'Étoile et le PCF, dont l'appareil ne peut tolérer une organisation qui échappe à son contrôle. On peut aussi imaginer que la radicalité du programme de l'ENA posait problème. En tous cas, à cette date, l'ENA regroupe déjà plus de 3000 militants.

Une telle organisation ne pouvait qu'inquiéter au sommet de l'État. L'ENA est donc dissoute le 20 novembre 1929 au nom de la « menace pour l'autorité de l'État » qu'elle représentait. Mais cette première dissolution reste sans effet.

Durant les années 30, l'ENA participe aux différents mouvements de classe qui se succèdent. Elle maintient des liens constants avec la S.F.I.O. et le P.C.F. qui lui fournissent une certaine aide matérielle. Avec le P.C., l'interlocuteur privilégié des messalistes est A. Ferrat, qui dirige sa section coloniale. Mais, partisan de la décolonisation, Ferrat est exclu en 1936.

En janvier 1937, le gouvernement du Front Populaire dissout l'ENA, qui compte alors 5000 membres. Mais dès mars 1937, Messali constitue le Parti du Peuple Algérien, qui se situe dans la continuité de l'ENA.