Labiénus exécuta les ordres de son chef avec sa ponctualité coutumière. Il laissa à Sens, pour garder les bagages, les soldats de l’année, et il suivit avec ses quatre légions la rive gauche de l’Yonne.
Au delà du confluent de la Seine, encore que le territoire des Parisiens ne commence qu’aux marais de l’Essonne, Labiénus n’a plus que des ennemis au-devant de lui. Les Sénons révoltés occupent leur ville de Meclosédum (Melun), bourgade bâtie comme Lutèce dans une île de la Seine, une sorte de réplique de la cité parisienne. De l’autre côté de l’Essonne, les Parisiens et tous leurs voisins de la Gaule propre, les peuples du Maine, de la Normandie et de l’Armorique, ont dès le premier jour fait cause commune avec Vercingétorix, et il est probable que le gros de leurs milices, ainsi que celles du pays sénon, ont été laissées par lui pour défendre ces territoires.
Labiénus se hâtait afin d’empêcher la concentration de ces troupes. Il resta sur la rive gauche pour s’épargner le passage de la Seine et de la Marne; il négligea de prendre Melun, d’ailleurs peu redoutable; il ne se donna même pas le temps de faire main basse sur la flottille de barques amarrées à cet endroit. Mais, malgré tout, les Gaulois le devancèrent.
Durant toute cette campagne de 52, ils ont montré en effet, au Nord comme au Sud, une réelle aptitude à se concentrer rapidement. Ces nations, comme les Samnites et les Romains des temps héroïques, vivaient toujours dans l’attente de la guerre prochaine: les milices étaient prêtes à répondre à un signal qui revenait, chaque année, presque aussi sûrement que le cri de l’hirondelle.
Une importante armée s’était réunie à la nouvelle du départ de Labiénus. Ce n’étaient pas des troupes tumultuaires, mais des soldats aguerris, braves et tenaces, fort supérieurs aux brillants cavaliers du pays éduen. Ils choisirent pour chef Camulogène l’Aulerque: c’était un très vieux général, et qui détonne dans cette insurrection de la Gaule où la jeunesse se tailla tant de commandements; mais on l’aimait à cause de sa longue expérience et de sa science consommée des choses de la guerre.
Il justifia sur-le-champ son renom et son autorité. Ce fut sans doute à Paris que se fit le rassemblement des forces gauloises. Camulogène réfléchit, étudia le pays, et attendit Labiénus sur la rive de ce marais vaste, long et continu que forme l’Essonne avant de se jeter dans la Seine: c’était un obstacle presque aussi insurmontable que la montagne de Gergovie. Les Romains avaient à lutter là-bas contre les rochers et ici contre le marécage.
Labiénus essaya du moyen classique pour franchir les palus: il voulut, sous la protection des mantelets, charger un chemin sur claies et fascines. Au bout de quelques heures de travail, il reconnut que c’était peine perdue, et il décampa sans bruit au milieu de la nuit, pour faire ce qu’il aurait mieux valu décider dès son départ de Sens: s’assurer les deux rives du fleuve, et la descente par terre et par eau.
Il rétrograda jusqu’à Melun. Le pont était coupé, ceux des habitants qui n’avaient point rejoint Camulogène s’étaient réfugiés dans l’île. Mais ils avaient eu l’imprudence de ne pas détruire les barques. Labiénus en saisit une cinquantaine, les remplit de soldats, enleva la bourgade épouvantée, et reprit sur la rive droite sa marche vers Paris, la flottille descendant le fleuve avec lui.
Camulogène, averti par des fugitifs de Melun, adopta la tactique préconisée par Vercingétorix. Il envoya l’ordre d’incendier Paris, de détruire les ponts, et alla se poster sur la rive gauche de la Seine, au pied de la montagne Sainte-Geneviève (aux Grands-Augustins?). Labiénus était déjà campé sur l’autre rive, en face de la pointe de la Cité (vers Saint-Germain-l’Auxerrois?).
La lutte allait s’engager entre les deux adversaires pour la possession, non pas de la ville réduite à rien, mais de ce carrefour de routes fluviales qui y aboutissaient, et la question de Paris était presque aussi grave que celle de Gergovie.