Après avoir travaillé à l’Ontario, Simcoe and Huron Rail-Road, Sandford Fleming met ses talents à profit pour un autre tronçon de chemin de fer d’une importance capitale : l’Intercolonial, reliant les Maritimes au Canada-Est. Fleming est arpenteur en chef.
Parmi 15 itinéraires possibles, il propose en 1865 celui qui longe la baie des Chaleurs, traverse la vallée de la Matapédia et rejoint le Saint-Laurent. Fleming devient par la suite ingénieur en chef responsable de la construction d’une partie du chemin de fer.
Il doit régulièrement se rendre à Ottawa pour défendre ses décisions. Une querelle mémorable l’opposera aux commissaires ferroviaires qui supervisent le projet au sujet des matériaux à utiliser pour les ponts ferroviaires.
Fleming travaille pour l’Intercolonial jusqu’à son ouverture en 1876.