À partir de ces bases, sa colonne, qui compte notamment le capitaine MASSU, effectue des raids de plusieurs milliers de kilomètres au milieu du désert, avec un équipement peu adapté aux conditions climatiques et au sol sableux et se dirige vers des postes italiens. Koufra, au milieu du désert, est un modeste fort tenu par une garnison italienne et protégé par une compagnie motorisée qui vadrouille en couverture dans la région , la Sahariana. C’est sans doute le poste le plus avancé, au sud, de l’alliance germano-italienne.
LECLERC se lance dans le désert avec une centaine d’Européens et 250 méharistes et tirailleurs «sénégalais», essentiellement des Tchadiens et des Camerounais. La petite troupe est équipée de bric et de broc avec quelques dizaines de vieux véhicules, cinq petits avions, des armes et des uniformes à l’avenant.
Les Français combinent leur action avec les Britanniques qui, du Caire, lancent une attaque sur Mourzouk, la capitale du Fezzan. Le major CLAYTON, qui commande la colonne britannique, se fait «prêter» par LECLERC deux officiers : le capitaine MASSU, qui se rendra plus tard célèbre en Algérie, et le lieutenant-colonel Colonna d’ORNANO, qui sera tué devant Mourzouk.
La colonne britannique est défaite par la Sahariana sans atteindre son objectif et les rescapés rejoignent la colonne de Leclerc. Celle-ci arrive le 7 février 1941 en vue de Koufra.
Jouant d’audace (comme à son habitude), LECLERC tient en respect les défenseurs du fort avec une partie de ses troupes. Lui-même et le reste de ses troupes éloignent la Sahariana du fort. Après un ultime combat, le 19 février, la compagnie motorisée décroche et se replie vers le nord-ouest. Les défenseurs de Koufra ne peuvent plus compter que sur eux-mêmes. Ils surestiment le nombre et l’équipement de leurs assiégeants et Leclerc les entretient dans leur ignorance en faisant déplacer sans cesse ses armes automatiques.
Le 1er mars, enfin, des parlementaires sortent du fort et demandent aux Français leurs propositions pour une reddition dans l’honneur. Les palabres s’éternisent. À la fin, n’y tenant plus, LECLERC surgit parmi les négociateurs et ordonne aux Italiens de remonter dans leur véhicule. Lui-même s’asseoit à leurs côtés avec deux officiers et leur commande de regagner le fort. Les Italiens, estomaqués par cette entorse aux usages, s’exécutent.
Arrivé en présence du commandant du fort, Leclerc impose ses conditions. La capitulation est signée le jour même. La garnison défile à 14h devant Leclerc : 11 officiers et 18 soldats italiens, 273 Libyens. Les combats lui ont occasionné 3 tués et 4 blessés. Les pertes du côté français ont été de 4 tués (dont un Européen) et de 21 blessés.
Le lendemain, c’est au tour du détachement français de se rassembler dans la cour du fort. Après avoir fait hisser les couleurs, le colonel LECLERC prononce une allocution mémorable qui se termine par ces mots, quelque peu surréalistes en ce morceau de désert saharien : «Nous sommes en marche, nous ne nous arrêterons que lorsque le drapeau français flottera sur la cathédrale de Strasbourg». Les soldats et officiers reprennent le serment à la suite de leur Chef
Aussi modeste soit-elle, la bataille de Koufra a un impact symbolique immense pour les Français en lutte contre l’occupant car c’est le premier succès militaire des Français Libres. 
Le général de Gaulle ne s’y trompe pas. Dès le 3 mars, il télégraphie à Leclerc un message de félicitations qui se termine par ces mots inhabituels chez lui : «Les glorieuses troupes du Tchad et leur chef sont sur la route de la victoire. Je vous embrasse».
Le 16 juin 1941, il est déchu de la nationalité française par un décret du gouvernement de Vichy. Le 11 octobre suivant, la cour martiale de Gannat le condamne à mort par contumace et à la confiscation de ses biens pour « crimes et manœuvres contre l’unité et la sauvegarde de la patrie » [«