Il y eut six grands commandements, aux titulaires desquels on conserva leurs anciens titres; ce furent le Cheikh-el-Arab, commandant la région de Biskra ; les caïds des Haractas et des Hanenchas, grandes confédérations de la frontière tunisienne; les khalifas du Sahel, entre l'Edough et Djidjelli, du Ferdjioua, au Nord-Ouest de Constantine, de la Medjana entre Sétif et les Portes de Fer. Les plus considérables de ces commandements étaient celui du Cheikh-el-Arab, que Valée confia à Farhat-ben-Saïd, remplacé en 1840 par Bou-Aziz-ben-Gana, et celui de la Medjana, dont l'investiture fut donnée à Mokrani.
Ces grands chefs étaient des vassaux plutôt que des fonctionnaires. Il y avait, entre la France et les khalifas, une sorte de contrat synallagmatique; ils étaient les " lieutenants " du général commandant la province, assimilés à des généraux de brigade, ayant dans leur commandement les honneurs attribués aux khalifas sous le gouvernement des beys.

La solution adoptée par Valée se justifiait par le fait que la métropole demeurait toujours attachée à l'occupation restreinte et refusait aux généraux les moyens d'action nécessaires; il fallait donc recourir à des procédés pratiques et peu dispendieux. Ce que nous recherchions alors, ce n'était ni des administrateurs, ni des fonctionnaires : c'était des alliés puissants et influents, des gens dont le nom, les antécédents, la situation familiale nous fissent accepter par les populations. A ces alliés, qui venaient nous offrir des pays que nous ne connaissions pas et dans lesquels on ne nous avait jamais vus, nous ne pouvions demander autre chose qu'un concours politique et militaire.