Au début de l'année 1956, la France se trouve engagée dans une forme nouvelle de conflit sur le territoire algérien : la guérilla. Conscient des capacités nécessaires pour mener cette nouvelle sorte de guerre et voyant les possibilités que peuvent apporter les hélicoptères dans ces engagements d'un nouveau type, le général de Maricourt, commandant l'Air en Algérie, propose un nouveau concept d'action pour les troupes aériennes qu'il résume par la formule : "il est plus facile à un oiseau de marcher qu'à un serpent de voler". Il s'agit d'armer les hélicoptères qui auront à transporter des hommes capables d'interventions rapides. Ces combattants seront des aviateurs.
L'idée du général de Maricourt ayant été retenue après de longues interrogations, l'armée de l'air créé le 12 mars 1956 une première unité d'infanterie de l'air de type "commando". Ainsi, le 15 mai 1956 l'instruction n° 6168/EMAA/1, signée du Général Jouhaud, major général de l'Armée de l'air, porte-t-elle création des commandos 10/541 et 20/541. La numérotation "541" est celle attribuée par l'Armée de l'air aux unités affectées au maintien de l'ordre en A.F.N. L'instruction n° 6969/EMAA/1 du 25 juillet 1956 porte création du commando 30/541. En 1957, sont créés le CPA 40 puis le (G.C.P.A. 00/541). Enfin, en 1959, le CPA 50, issu d'un commando expérimental mis sur pied en l'année précédente.
Chaque commando, destiné à être transporté par hélicoptère et à combattre au sol, doit être composé d'une centaine d'hommes. Il est articulé en un certain nombre d'éléments simples de 5 ou 6 hommes qui constituent l'équipe. Le groupe de commando est formé, quant à lui, de 2 équipes ; ce qui correspond au chargement de deux hélicoptères H-19 ou d'un hélicoptère H-34. La section de commando est constituée de 4 équipes : deux équipes de commandement et feu avec l'officier-chef de section à la tête de l'une d'elle et deux équipes de commandos.
La prospection est effectuée parmi le personnel de l'Armée de l'air de toutes spécialités. Le recrutement se fait par acte de volontariat. La sélection est particulièrement sévère et les limites d'âges sont basses : 25 ans pour les hommes de troupe. Les aptitudes médicale, caractérologique et physique sont très sérieusement contrôlées. Enfin, la durée minimale du lien au service est portée à 15 mois. Pour différencier les commandos parachutistes de leurs camarades des autres armes, ils portent un béret bleu marine.