Au 1er Régiment Etranger, le jeune officier découvre un monde tout différent de ce qu'il a connu en métropole. Dans ces postes du sud algérien la vie est plus chaleureuse, plus communautaire, plus dure aussi. Une bande de lieutenants entoure le nouvel arrivant. Ils ont encore dans leur amitié et dans leur conduite l'effervescence d'adolescents. Ils distribuent des surnoms : Molleron pour Rollet, Le Vigoureux pour Diard, La Grosse pour Gaubert, Verton pour Verries."A Aflou, à Tiaret", écrit Diard "l'on bouffe, bidonne à hauteur, on organise des parties avec les ménages, chasse au renard, rallyes, etc…" Comme dans toutes les étapes ultérieures de sa carrière, Rollet adopte un chien, puis deux Djenan et Zoubilia.

Mais plus que ces agréments de la vie courante cette chaleur amicale du mess, c'est la découverte de sa nouvelle troupe et la vie en campagne qui marquent à jamais le Lieutenant Rollet. Le décor d'une nature difficile et qu'il faut maîtriser, l'exercice des responsabilités sur le terrai, les efforts exigés des autres comme de soi-même, une camaraderie mais aussi une émulation de chaque instant, des chefs qu'il peut respecter mais qui savent aussi gagner son cœur… Non ! Paul Rollet ne regrette pas Mézières.

En 1900, il a la chance d'être désigné pour faire colonne sur Igli, sous les ordres du grand Brundsaux, déjà légendaire à la Légion après la campagne du Dahomey et qui va bientôt partir pour Madagascar. Chef à la fois dur, expansif et généreux, qui a su se faire un personnage et "une gueule" appréciés des légionnaires, il a très certainement profondément impressionné son "boufadi" de lieutenant au point de devenir l'un de ses modèles. Peut-être même est-ce pour le suivre qu'en 1902, le jeune homme devenu chef de file de ses pairs entraînés par son ardeur, son culot et son sens du panache, va partir à son tour pour rejoindre le bataillon de Légion de Madagascar. Un petit scandale de garnison servira de prétexte à cette mutation : les distractions turbulentes de la bande pendant les entractes de leur vie de guerriers, de découvreurs et de patrouilleurs de pistes et de djebels sont peut-être trop épicées pour le tempérament des civils, qui commencent à s'embourgeoiser.