Le Train en Afrique du Nord, en plus des missions traditionnelles du Train, c'est aussi la création de 8 Bataillons de Marche dont les Tringlots vont crapahuter comme fantassins. Ces unités composées de rappelés, d'appelés, de rappelés, de harkis, commandés par des gradés appelés et engagés, ont reçues une instruction d'infanterie limitée (gradés compris). Comme leurs camarades des bataillons de marche de l'Armée de l'Air, comme leurs camarades des bataillons de la Marine, ils devront s'aguerrir au fil du temps pour devenir des unités d'intervention au même titre que les Parachutistes ou la Légion. Comme il n'y a pas assez de Tringlots, des appelés et des réservistes d'autres armes vont être mutés d'office dans le Train.

Ce rappel ne va pas sans créer des problèmes dans la population métropolitaine. Dès que les premières feuilles de route arrivent chez les intéressés, le mécontentement est général. Dès les premiers convois, des grèves éclatent à Rouen, à Saint-Nazaire (20 blessés). Des manifestations se déroulent dans les gares de rassemblement, à Metz au départ du 94e Régiment d’Infanterie, à Lézignan, à Paris, à Rouen (2 jours d'émeute contenus par 300 C.R.S.), à Dreux pour le départ des rappelés des dépôts d’Évreux, Chartres et Vernon, à Avignon, à Fréjus, à Montpellier, à Grenoble, à Bar le Duc, à Dijon, au Mans (10 blessés). Des familles se couchent sur les voies pour empêcher le départ des trains. Les C.R.S. et les gendarmes mobiles interviennent. Les rappelés tirant sur le signal d’alarme arrêtent les trains en rase campagne. Il faut des heures pour parcourir quelques kilomètres. Ces rappelés qui ont quitté le service actif depuis plusieurs mois (jusqu'à deux ans pour certains), parfois chargés de famille, avec les soucis de la vie quotidienne, quittent femme et enfants pour rejoindre des locaux où rien n’est prêt. A Rouen, la caserne Richepanse qui les accueille est en ruines. Des mesures sont cependant rapidement mises en place : prise en compte des difficultés sur le plan fiscal, instauration de la franchise postale, amélioration de la solde. Ces manifestations dont la presse fait un large écho ne concernent en réalité souvent peu de monde, quelques dizaines de personnes tout au plus, au mieux quelques centaines.

Les manifestations sont vaines, les rappelés savent eux que c’est peine perdue, même “s’ils n’en ont rien à foutre des colonies”. Ils ne comprennent pas très bien pourquoi ils sont rappelés, au nom de quel principe, pour qui, pour quoi, mais ils feront leur devoir ? Parmi eux certains sont déjà venus en Algérie ou tout au moins en Afrique de Nord au titre de leur service militaire normal. Résignés, ils continuent leur route en direction de Marseille, Sète et Port Vendres, avec les appelés des contingents 1955 et 1956. Si l’opinion publique se polarise sur les rappelés, elle oublie les appelés directement en Algérie. Ces appelés ne sont pas passés par un centre d’instruction et débarquent sans connaissances militaires. Ils apprendront en Algérie.

Fin 1956, 4 900 officiers, sous-officiers et hommes de troupe du Train servent comme fantassins dans les :

Tout d'abord avec des rappelés, le Train constitue des bataillons de 700 hommes (sur le papier, car en réalité moins) qui seront remplacés après le départ des rappelés par des appelés du contingent. Avec eux, les effectifs des bataillons passent à un millier d'hommes. Il est créé également un Bataillon de Protection chargé de l'ouverture des voies ferrées et de la protection des déplacements ferroviaires. Chacune des autres unités du Train va également constituer une section de harkis. A la fin de 1956, l'ensemble des bataillons de marche comprend 140 officiers, 660 sous-officiers et 4 100 hommes (8% des effectifs du Train).

A l'indépendance de l'Algérie, les Bataillons de marche sont dissous et leurs effectifs répartis dans les groupes de transport ou les compagnies de circulation.