À Brazzaville, en octobre 1940, de Gaulle décide la création d'une "Brigade française d'Orient" (BFO), placée sous les ordres du colonel Magrin-Verneret, destinée à être mise à la disposition du commandement britannique au Moyen-Orient. À la mi-février 1941, elle retrouvera au Soudan le BM 3 du commandant Garbay, parti de Fort-Lamy, déjà à pied d'œuvre au sein de la brigade indienne du général Briggs. C'est le BM 3 qui enlèvera huit jours plus tard le fort italien de Kub- Kub, première victoire française libre contre les troupes de l'Axe, qui va ouvrir à la BFO la route de Keren.

Rassemblée le 6 mars au camp de Chelemet, à une dizaine de kilomètres de Kub-Kub, la BFO s'élance à l'assaut de Keren six jours plus tard. Après une progression pénible, dans une région aride et montagneuse, la Brigade livre ses premiers combats contre les Italiens retranchés sur deux hauteurs, le Grand Willy et le Petit Willy, dont deux compagnies de Légion (capitaines de Lamaze et de Bollardière) vont s'emparer le 14 mars. Les Italiens se replient sur une ligne de crêtes, dominée par l'Engiahat, dont la conquête est confiée à la Légion (les compagnies Morel et Lamaze, soutenues par l'artillerie de la compagnie Amilakvari) et à la 3e compagnie du BIM (capitaine Savey). Avantagés par leur position, les Italiens résistent farouchement. Entre temps, au Caire, le général de Larminat a décidé d'engager six avions du GRB 1 (capitaine Astier de Villatte) dans les opérations en Erythrée. Le 28 mars, l'équipage de Jean de Pange bombarde un camp italien de la région de Gondar, au nord du lac Tana ; dans les jours suivants, des coups directs détruiront des campements militaires sur la route de Gondar à Asmara.

Au sol, les combats ont repris le 27 mars. Cette fois, l'Engiahat est immédiatement occupée et la poursuite s'engage de manière à ne pas laisser aux colonnes italiennes en fuite le temps de se regrouper. Au matin du 28 mars 1941, Keren est occupée par les Français, qui font prisonniers une cinquantaine d'officiers et un millier d'hommes. Quelques jours plus tard, de Gaulle, arrivant de Londres, félicitera les hommes de la BFO rassemblés au camp d'Agordat. Le 2 avril, au Caire, il déclarera : "Jamais dans leur histoire les Français n'ont combattu avec plus d'élan."

La prise de Keren prélude à la conquête de l'Erythrée, achevée le 7 avril par la prise de Massaouah, le grand port éthiopien sur la mer Rouge. Le 10 avril, c'est au tour du général Platt, commandant les troupes britanniques, de passer en revue et de féliciter les Français. "Le succès de la Brigade, expliquera le général Simon, qui participa à cette campagne au sein de la Légion, était dû à la rapidité de l'action, à l'efficacité des appuis britanniques, à l'élan des Français libres, mais aussi à la démoralisation d'un adversaire acculé à la mer après plusieurs défaites." Les hommes de Magrin-Verneret avaient fait leurs preuves sur un terrain difficile, ils s'étaient acquis la confiance de l'allié britannique, ils pouvaient donc espérer être bientôt engagés dans les prochains combats contre l'Axe. Le 11 septembre 1944, de Gaulle écrira à Platt : "La route de Paris passait par Keren."