En 1875, soutenu par le gouvernement, il remonte le fleuve Ogooué au Gabon. En 1879, c’est sur le Congo qu’il se lance, négociant pacifiquement des traités de protectorat avec les chefs locaux. Une véritable course pour le contrôle de ce cœur du continent s’ouvre avec le Britannique Stanley au service, lui, du roi des Belges.
Plantant le drapeau tricolore au milieu de ses campements successifs, Brazza déclare libérer de l’esclavage tous ceux qui en toucheront le mât ou les plis.
Contraint de retourner en métropole pour lever de nouveaux fonds, il laisse le poste qu’il occupe sur la berge du fleuve – qui deviendra la capitale Brazzaville – à la garde de son compagnon d’aventure, le sergent de tirailleurs sénégalais Malamine.
En 1881, Stanley, furieux d’avoir été précédé, tente sans succès d’intimider le sergent. Le tirailleur lui tient tête et après bien des péripéties, le Congo constituera la pièce maîtresse de l’Afrique équatoriale française.
Brazza l’explorateur, le libérateur des esclaves, et Malamine, le fidèle tirailleur, entrent dans le légendaire colonial. Ils sont les premiers d’une geste réunissant le héros blanc et le brave soldat noir, diffusée sur d’innombrables supports, presse, littérature, chansons, théâtre, affiches, gravures, vignettes et plus tard photos et films…