Zamiast tego został głównym inżynierem budowy wielu linii kolejowych we wschodniej Kanadzie, między innymi Kolei Interkolonialnej. W czasie projektowania i budowy linii kolejowych niestrudzenie stał na stanowisku budowy stalowych mostów i wiaduktów zamiast, jak to było w ówczesnej praktyce, drewnianych. W 1885 został członkiem zarządu Canadian Pacific Company – przedsiębiorstwa kolejowego zarządzającego Koleją Transkanadyjską. Był obecny przy uroczystości wbijania „ostatniego gwoździa” kończącego budowę tej linii kolejowej.
W 1878 po tym, jak spóźnił się na pociąg, przyszedł mu do głowy pomysł czasu uniwersalnego i stref czasowych. Zreferował go na konferencji Kanadyjskiego Królewskiego Instytutu. Pomysł przyjęto z zainteresowaniem. Od tego czasu Fleming z wielką energią zabrał się do wprowadzenia swojej idei w życie. W 1884 system ten został zaakceptowany na całym świecie. Był także pomysłodawcą i promotorem połączenia Ameryki Północnej i Wielkiej Brytanii transatlantyckim kablem telegraficznym. Projekt ten został ukończony w 1902.