En 1946 creouse a Compagnie Générale de Transports Aériens (CGTA). Comezou a realizar voos chárter entre Alxeria e Europa no ano seguinte, pero cara finais da década xa tiña voos regulares servindo a Alxer, Basilea, Annaba, Xenebra, Marsella, París, Philippeville e Tolosa. Tres Bretagne de 34 asentos uníronse á frota de sete DC-3 en 1952. A Compagnie Air Transport (CAT), subsidiaria de Air France e a Compagnie Générale Transatlantique, formouse a finais dos 40 para conectar Basilea, Lión, Marsella, París e Tolosa con Alxer, Constantine e Orán. Tamén se iniciaron voos estacionais entre Londres e Deauville. Tras a caída de trafico despois de 1951 comezouse a considerar un socio para fusionarse.[3]
Constellation coa librea de Air Algérie en 1957
CGTA e CAT fusionáronse o 23 de maio de 1953 para formar a Compagnie Générale de Transports Aériens Air Algérie,[3] cunha frota combinada que incluía un Breguet 761, seis Bretagne, cinco DC-3 e tres DC-4. Tras a fusión, Air Algérie comezou servizos estacionais cara Ajaccio, Clermont, Montpellier e Perpignan. Ademais, engadíuse a Suíza aos voos regulares, realizouse unha parada semanal en Palma de Mallorca coa súa asociación con Aviaco, e a meirande parte das rutas transmediterráneas foron operadas nun acordo con Air France, facendo a aeroliña francesa o 54% deses voos e Air Algérie o resto. A finais dos 50 engadíronse tamén voos a Cote d'Azur.
A aeroliña mercou dous Nord Noratlas en xullo de 1957, chegando un terceiro un ano despois. A compañía converteuse na primeira aeroliña privada francesa en pedir o Sud Aviation Caravelle a comezos de 1958, e o primeiro exemplar lle sería entregado polo fabricante en xaneiro de 1960. Tras a entrega o avión foi usado na ruta entre Alxer e París. O modelo tamén utilizouse nos voos entre París e Bône e París e Orán nos meses seguintes. Cara abril de 1960 a súa frota estaba formada por tres Caravelle, tres DC-3, dez DC-4, dous Lockheed L-749 Constellations e tres three Noratlas. Os Caravelle foron gradualmente despregados nas rutas anteriormente voadas polos Constellations e os DC-4, que foron usados para carga ou vendidos.[3]
Dúas compañías navieiras, Compagnie Générale Transatlantique e Compagnie de Navigation Mixte, foron as donas da meirande parte das accións (98%) de Air Algérie ata que o país se independizou en 1962. Tras a independencia a Délégation Générale en Alxeria e Air France tomaron o da meirande parte da compañía. A estrutura financeira cambiou en marzo de 1963, cando as navieiras e Air France cederon un 31% da aeroliña,[24] e o goberno arxelino tomou posesión do 51% dos activos da empresa, gañando o status de aeroliña nacional. En abril de 1964 o goberno incrementou a súa participación ata un 57%.[4] Ese nes asinouse un contrato para a compra de dous Ilyushin Il-18 destinados a operar a ruta entre Alxer e Moscova.[5] Air Algérie so recibiría un destes avións, xa que o contrato foi posteriormente cancelado. O único Il-18 da frota foi usado polo goberno. En abril de 1968 había oito DC-4 na frota e ese ano catro Convair 440 ex-Lufthansa foron mercados e convertidos á versión 640. Eses avións substituirían aos DC-4.
Cara marzo de 1970 o goberno era o dono do 83% da compañía; nese momento a frota estaba omposta por un Boeing 737-200, cinco Caravelle, catro CV-640, tres DC-3 e un DC-4.[6]Société de Travail Aérien, unha aeroliña doméstica que fora fundada en 1968, foi absorvida por Air Algérie en maio de 1972. No mes de agosto pedíronse tres Fokker F27-400 por 2,5 millóns de libras. En setembro, cun segundo Boeing 737 pendente de entrega, pedíronse dúas unidades máis dese modelo (un deles convertible). Ese ano o goberno de Alxeria mercou as accións restantes posuídas por Air France e fíxose co 100% da aeroliña. Air Algérie abriría unha nova ruta a Karachi en 1975, e en novembro de 1979 pedíronse catro Boeing 727 por 62 millóns de dólares.[7]
