臺灣總督府計畫運用民間資金興建縱貫線的計畫宣告失敗後，後藤新平在明治卅二年（1899年）3月向日本帝國議會提出〈臺灣事業公債法〉，預計在二十年內募資6千萬元的公債來作為臺灣總督府在臺建設的資金，其中3千萬圓為鐵路修築費用，之後該預算被帝國議會砍為以十年募集3千5百萬圓，鐵路費用則被刪減了120萬圓。在此同時，臺灣總督府也在該年3月30日成立「臨時臺灣鐵道敷設部」來負責興建縱貫線，臺灣鐵道會社見此，遂建議總督府收購該會社之股份與設備，之後在同年10月25日宣告解散。而臨時臺灣鐵道敷設部在該年11月與民政局的臨時鐵道掛合併，正式成立鐵道部。
縱貫線的路線大致上是依照早期探勘的「山線」鋪設，但有部分路段因時空背景因素而有所更動，工程則從北部與南部分頭進行。而由於當時臺灣各港口的狀況無法符合日方的需求，導致材料的輸入相當困難，大船只能停在外海，由小船接運，海象惡劣時除了小船無法出航外，大船也無法停泊只能開回出發地。而即使材料運上岸了，也因為當時臺灣的道路狀況相當原始，所以只要情況允許鐵道部便會盡可能修建鐵路（輕便鐵道）來搬運材料，而淡水線（北淡線）即是當年的材料搬運線之一。淡水線在明治卅四年（1901年）8月25日完工開業，但到了該年10月25日才與臺北－桃園段的改良線一同舉辦「開通式」。臺北新竹段由於淡水溪橋在1897年、1898年8月都被沖斷過，與龜崙嶺一帶的高坡度，而使得鐵路路線改為經過艋舺、枋橋街（今新北市板橋區）的現行路線到桃仔園，而由於鳳山溪一帶的鐵、木橋在明治卅一年（1898年）8月也被沖斷，所以直到明治卅五年（1902年）2月1日將鐵道橋修好前，南下的火車只到鳳山崎新設的「新車」車站，之後再坐船過河前往新竹，而在這段時間新車到新竹的鐵路曾鋪設輕便鐵道應急，鐵道橋修好之後，鐵路營運路段在該年8月從新竹延伸到中港溪附近，於8月10日新設香山、中港（今竹南車站）二站。而後縱貫線繼續向南延伸，明治卅六年（1903年）5月25日完成中港苗栗段，隔年（1904年）推進至三叉河（今苗栗縣三義鄉），縱貫線的工程原本預定要耗費十年，但結果提早一年完工，耗用經費也比預估的少，遂將經費投入基隆車站的改建與臺灣鐵道飯店的興建，此外由於縱貫線未經過南部要地鳳山廳行政中心鳳山街，遂興建打狗（今高雄港車站）到九曲堂的「鳳山支線」（工程期間為1907年4月到9月），該支線後來延伸成屏東線。而縱貫線的興建，基本上是奉行「速成延長主義」，盡可能地要讓鐵道早日通車，故施工上要求越快越好，經費也是能省便省，故忽略了不少實際營運上可能會面臨的小問題，車站等設施也都因陋就簡。而也就由於「速成延長主義」的因陋就簡，使得臺灣總督府鐵道在一開始便埋下日後變得體質不良、品質低下的遠因。
至於縱貫線南段則從明治卅二年（1899年）11月自打狗（今高雄鼓山區南部）往北鋪設，隔年（1900年）11月29日打狗臺南段開始營運，再隔年（1901年）5月15日營業路段沿伸至今善化車站。而到了明治卅七年（1904年）時南段路線已經延伸到了彰化，同時北段也到了三叉河，只剩下最後難度最高的中部路段，該路段之所以困難主要是因為三叉河到葫蘆墩之間需要渡過大安溪與大甲溪，且需開鑿許多隧道穿越山區。
而在縱貫線最後的中部路段施工時，適逢日俄戰爭爆發（1904年2月8日），由於俄羅斯太平洋艦隊遭到重創，沙皇尼古拉二世遂命波羅的海艦隊到東亞支援，因其航線會經過臺灣的關係，日本方面遂在基於國防需求下動用臨時軍事費興築伯公坑到葫蘆墩的輕便鐵道（又在此之前已有伯公坑到三叉河的輕便鐵道），該路線於明治卅九年（1906年）完工後，除了軍事用途外，也用來搬運建材與兼營客運，此外該路線為了在大安溪南岸爬上后里臺地，還設計了圓弧型引道，為其特色。而在明治四十一年（1908年）3月，九號隧道完工後，縱貫線全線在該年4月20日完工通車。
