La conquête du Fezzan, première campagne (février-mars 1942)
Revenu à Fort-Lamy, Leclerc se consacre, dans les mois qui suivent, à sa prochaine mission : le Fezzan. L'opération contre Koufra a été une magnifique affirmation de la volonté de combat des Français libres ; la conquête du Fezzan est une nécessité imposée par l'avancée des Britanniques en Libye* : "S'ils réussissaient à atteindre la frontière tunisienne, il serait essentiel que nous y soyons avec eux, ayant, au préalable, aidé à battre l'ennemi. Si, au contraire, celui-ci parvenait à les refouler, nous devrions tout faire pour concourir à l'arrêter avant qu'il ne submergeât l'Egypte." (Mémoires de guerre) En réalité, de Gaulle ne croit pas au succès de la contre-offensive britannique, et les événements lui donnent raison : à la fin de janvier 1942, avec une Afrikakorps intacte, Rommel repart à l'assaut de l'Egypte.

La mission de Leclerc change dès lors de nature : puisque la jonction avec les forces britanniques est, pour l'instant, inenvisageable, il ne lui reste plus qu'à exécuter une opération de "va-et-vient" sur le Fezzan, qu'il définit ainsi le 1er février : "assez forte pour sonner l'adversaire et obtenir des renseignements utiles, assez faible pour permettre une reconstitution rapide du stock d'essence au cas où l'opération initiale serait reprise". Il monte cette nouvelle opération en deux semaines avec sa précision et sa rigueur habituelles. À partir du 15 février, quatre patrouilles de dix voitures (commandées par les capitaines de Guillebon, Massu et Geoffroy), appuyées par onze avions du groupe "Bretagne", vont porter à un ennemi distant de plus 600 km des coups sévères et inattendus. Le général Vézinet, qui y participa, racontera : "Des petites colonnes motorisées partaient du Tchad en se camouflant, arrivaient par surprise au pied d'un poste italien, s'en emparaient et brûlaient le poste, libéraient les combattants indigènes et faisaient prisonniers les Italiens" Les Français s'emparent ainsi de deux postes importants : Gatroun et Uigh el-Kébir.

Le bilan de cette première campagne, qui s'achève à la mi-mars 1942, est largement positif - une "réussite complète", estime de Gaulle, qui ajoute : "Général Leclerc, vous et vos glorieuses troupes êtes la fierté de la France". Le 25 mars, Leclerc est nommé commandant supérieur des troupes de l'Afrique française libre. Il rejoint Brazzaville, en obtenant de De Gaulle la nomination d'un de ses fidèles, le colonel François Ingold, à la tête des troupes du Tchad.

La conquête du Fezzan, seconde campagne (septembre 1942-janvier 1943)
Le 22 septembre 1942, alors qu'il se trouve à Brazzaville, de Gaulle ordonne à Leclerc d'achever la conquête le Fezzan et de s'emparer de Tripoli, où il fera sa jonction avec les troupes britanniques. Envisageant l'hypothèse d'un échec du futur débarquement anglo-américain en Afrique du Nord, de Gaulle songe déjà à mettre en œuvre tous les moyens pour arracher à Vichy l'Afrique occidentale ; il prescrit donc à Leclerc d'envoyer des troupes au Niger et de préparer les unités qui interviendront à Madagascar : "C'était beaucoup de choses à la fois. Mais nous ne doutions de rien. Les Français libres d'Afrique constituaient un faisceau qu'aucune épreuve ne pourrait rompre." (Mémoires de guerre) Le 10 novembre, deux jours après le débarquement en Afrique du Nord - dont la France Libre a été écartée ** - de Gaulle demande à Leclerc de se tenir prêt à exécuter l'opération de ralliement du Niger : "Nous devons marquer par une action immédiate, explique-t-il, que nous n'admettons pas la reconstitution de Vichy en Afrique du Nord et en Afrique occidentale française sous la coupe des Américains. "Cependant, quatre jours plus tard, il change d'avis : il ordonne à Leclerc de préparer l'offensive au Fezzan, avec exploitation éventuelle soit vers Tripoli, soit vers Gabès (Sud tunisien), en liaison avec la 8e armée britannique et, éventuellement, avec les forces américaines d'Algérie. L'opération présente de sérieuses difficultés : les hommes de Leclerc doivent parcourir un millier de km, en emportant vivres, munitions, carburant ; ils doivent coordonner leur avance avec les troupes britanniques qui progressent en Cyrénaîque et il est impérativement demandé à Leclerc de refuser toute prétention des Alliés d'administrer le Fezzan libéré : "Le Fezzan doit être la part de la France dans la bataille d'Afrique, explique de Gaulle. C'est le lien géographique entre le Sud tunisien et le Tchad. "L'offensive commence le 22 décembre 1942 ; elle va durer deux semaines. Les groupements Ingold et Delange (4.000 Africains, 600 Européens), appuyés par le groupe d'aviation Bretagne, s'emparent de toutes les positions ennemies. Les Français entrent dans Sebha, principal centre militaire, le 12 janvier 1943 ; ils prennent Mourzouk, capitale religieuse, le lendemain. Vainqueurs sur toute la ligne, ils font un millier de prisonniers et s'emparent d'un matériel important. Mais surtout, la route de Tripoli leur est ouverte. Les Italiens sont chassés du Fezzan, désormais administré par le colonel René Delange ; les Anglais ne mettront pas la main sur ce que de Gaulle appellera, dans ses Mémoires de guerre, "ce fruit savoureux du désert". L'audace et la méthode ont payé.

Le 13 janvier 1943, de Gaulle exalte à la BBC l'épopée de Leclerc et de ses compagnons, "un exploit qui ne le cède en rien aux plus beaux de notre grande Histoire", assure-t-il, avant d'ajouter : "Avec la victoire de nos troupes du Tchad, l'ennemi a vu s'élever, une fois de plus, cette flamme de la guerre française qu'il avait crue éteinte dans le désastre et la trahison, mais qui, pas un seul jour, ne cessa de brûler et de grandir sous le souffle de ceux qui ne désespéraient pas. "A ses yeux, cette victoire n'est pas seulement un brillant fait d'armes, elle est aussi" un des signes avant-coureurs de cette France nouvelle, de cette France dure et fière qui se bâtit dans l'épreuve".
Le 25 janvier, les premiers Français venus du Tchad - après une marche de plus de 3.000 km - entrent à Tripoli, où Leclerc arrive dans la soirée. Le lendemain, il rencontre le général Montgomery, chef de la 8e armée britannique, vainqueur de l'Afrikakorps à El Alamein ; Montgomery le charge de prendre une part active à l'attaque de la ligne Mareth, qui défend le Sud tunisien. Le surlendemain, tandis que le capitaine d'Abzac, l'un de ses adjoints, occupe la grande oasis italienne de Ghadamès, Leclerc rend visite au commandant Bouillon, chef du Bataillon d'infanterie de marine et du Pacifique (BIMP), avant-garde de la 1re DFL, à l'aéroport de Tripoli : c'est la première jonction des FFL venues du Tchad et des FFL du Moyen-Orient.