Semenjak politik ekonomi liberal (1870) modal asing masuk ke pedalaman Pulau Jawa, pemerintah kolonial mulai memonopoli dan mengatur tata ekonomi. Kota Yogyakarta contohnya, mulai membangun berbagai fasilitas dan prasarana fisik kota. Seperti gedung kantor, tempat tinggal para pejabat serta layanan pendidikan (sekolah). Selain itu, segi transportasi juga mendapat perhatian. Pemasangan jalur kereta api oleh Nederlandsch Indische Spoorweg Maatschappih (NISM) dan Staatsspoor (SS), salah satunya adalah Stasiun Tugu.
Stasiun Tugu merupakan stasiun kedua yang dibangun oleh pemerintah kolonial di Yogyakarta. Stasiun pertama yang dibangun di Kota Gudeg adalah Lempuyangan pada 2 Maret 1872. Baru lima belas tahun kemudian, Stasiun Tugu dipergunakan pada 2 Mei 1887.
Stasiun Tugu dibangun oleh perusahaan kereta api milik negara Staatsspoorwegen (SS) pada 1887 di sebelah Barat Sungai Code yang membelah kota Yogyakarta. Sedang perusahaan Nederlandsch-Indische Spoorweg-Maatschappij (NIS) mempunyai stasiun sendiri di Lempuyangan, di sisi Timur Sungai Code. Meski demikian Stasiun Tugu digunakan bersama-sama oleh SS maupun NIS.
Stasiun Tugu adalah stasiun pulau dengan emplasemen di kedua sisinya, di Utara dan Selatan. Emplasemen Utara digunakan untuk jalur rel 1067 mm Westerlijen SS ke jurusan Bandung dan Batavia melalui Cilacap, serta jalur NIS ke Magelang, Secang, Parakan dan Ambarawa yang juga mempunyai lebar sepur 1067 mm. Emplasemen Selatan digunakan untuk rel 1435 mm NIS jurusan ke Surakarta, Kotagede dan Brosot. Pada 1929 di emplasemen Selatan di samping rel 1435 mm ditambahkan jalur rel 1067 mm untuk kereta api SS jurusan ke Surabaya lewat Surakarta.
Stasiun Tugu semula berarsitektur klasik. Beberapa waktu setelah pembukaannya surat kabar Bataviaasch Handelsblad 11 Oktober 1887 melaporkan bahwa Station Toegoe adalah stasiun paling anggun di Hindia Belanda. Di Stasiun ini terdapat ruang tunggu yang dulu digunakan oleh Sultan Yogyakarta dan tamu-tamu penting seperti Gubernur Jenderal Hindia Belanda. Ruang tunggu itu sekarang menjadi Ruang VIP.
Pada 1927 hall stasiun diperluas dan façade direnovasi menjadi bergaya Art Deco, di bawah pengawasan F. Cousin, kepala Biro Bangunan (Bouwkundig Bureau) Staatsspoorwegen. Cousin juga menangani modernisasi Stasiun Bandung yang antara lain merubah wajah depannya menjadi bergaya Art Deco. Arsitektur Art Deco yang populer di seluruh dunia antara 1925 dan 1940 ditandai dengan bentuk-bentuk geometris dan garis-garis lurus yang memberikan kesan modern dan mewah.
Pada 26 Desember 1959 diresmikan penggunaan terowongan di bawah emplasemen Selatan untuk masuk dan keluar penumpang dari dan ke Jalan Pasar Kembang tanpa harus menyeberang rel. Terowongan ini sempat tidak digunakan selama bertahun-tahun tapi sejak November 2011 sudah direnovasi dan difungsikan kembali. Di dekat ujung selatan terowongan pada bangunan terpisah terdapat pusat reservasi tiket.
Bagian tengah stasiun dinaungi atap besar dengan bentangan berbentuk busur selebar 21 meter dari konstruksi, sedangkan peron di emplasemen Utara dan Selatan masing-masing dinaungi overkapping yang lebih kecil berbentuk pelana. Konstruksi atap dibuat oleh perusahaan I.J. Einthoven di Den Haag pada 1888. Overkapping asli ini telah mengalami beberapa kali perluasan. Selain itu sebagian lantai peron telah ditinggikan dan penutupnya diganti ubin keramik. Di sisi Barat bangunan stasiun telah dibangun pendopo limasan yang difungsikan sebagai ruang tunggu penumpang (Buku Stasiun Kereta Api Tapak Bisnis dan Militer Belanda Terbitan BPCB Jateng).