Kota Cilacap dipandang oleh pemerintah kolonial sebagai kota pelabuhan penting di Jawa. Kota yang berdiri sejak 1857 ini, terletak di pesisiran selatan pulau Jawa. Sebagai kota transit, menampung komoditas dari beberapa wilayah sekitarnya (Banyumas, Kedu, hingga Yogyakarta), di Cilacap dibangunlah stasiun lengkap dengan jalur kereta apinya. Pembangunan stasiun Cilacap dilakukan secara bertahap, ditangani oleh perusahaan kereta api negara Staatspoorwegen (SS).
Pada tanggal 16 Juli 1887 Gubernur Jenderal Otto van Rees meresmikan pembukaan jalur kereta api Yogyakarta- Cilacap melalui Maos. Dengan dibukanya jalur itu dua terhubunglah vorstenladen dengan dua pelabuhan utama di Jawa Tengah, Semarang di pantai Utara dan Cilacap di pantai Selatan. Pada 1894 jalur Cibatu-Maos selesai dibangun, dengan demikian terhubunglah Oosterlijnen (jaringan Timur) dan Westerlijnen (jaringan Barat) Staatsspoorwegen (SS) meski tak langsung karena harus melalui jalur Surakarta – Yogyakarta dari Nederlandsch-Indische Spoorweg Maatschappij (NIS), dengan jalur Maos-Cilacap sebagai jalur cabang.
Jalur lintas kereta api Yogyakarta – Cilacap ini merupakan kedua di Jawa Tengah setelah NISM. Rel sepanjang 187.293 km ini mulai dikerjakan pada tahun 1879 dan selesai pada tahun 1887 dengan menelan biaya 14.709.074,75 gulden. Pemerintah melanjutkan pembangunan rel dari Stasiun Cilacap menuju pelabuhan untuk transportasi barang ditetapkan pada tahun 1888.
Dengan tersambungnya jalur kereta api tersebut, perkembangan pelabuhan Cilacap mulai tampak pada akhir tahun 1888. Hasil kopra dari Residensi Bagelen Selatan dan Banyumas kemudian dikirimkan ke Cilacap untuk diekspor, yang sebelumnya ke ditujukan ke Semarang. Sebanyak tiga kapal memuat penuh kopra dari Cilacap untuk diekspor ke pasar Eropa. Dari Kutoarjo saja telah dibawa ke Cilacap sebanyak 71.000 pikul pada saat itu.
Salah satu alasan lain pemerintah membuka lintas kereta api Yogya-Cilacap ini adalah untuk memudahkan transportasi gula dari pabrik-pabrik daerah Yogya. Gula merupakan primadona komoditas ekspor dari daerah Yogyakarta. Selain itu, dengan adanya jalur kereta api dari Cilacap, pendistribusian barang impor mampu dilakukan dengan optimal ke beberapa daerah lain di Jawa.
Arsitektur bangunan Stasiun Cilacap yang pertama bergaya neo-klasik Empire seperti stasiun-stasiun SS yang lain di masa itu. Pintu masuk dan hall utama dengan langit-langit tinggi berada tepat di tingah-tengah, diapit ruang tunggu dan ruang-ruang lain di kiri dan kanannya. Peron dinaungi atap dengan kuda-kuda Polonceau dari besi.
Pada 4 Maret 1942 Cilacap dibom oleh pesawat udara Angkatan Laut Jepang. Di pelabuhan terjadi kebakaran besar dan lima kapal ditenggelamkan. Sebuah kereta api yang baru tiba di Stasiun Cilacap dari Cirebon juga dibom, yang mengakibatkan lebih dari 150 orang meninggal, sedang bangunan Stasiun Cilacap mengalami kerusakan parah. Tak lama setelah itu pada 8 Maret 1942 Belanda menyerah tanpa syarat pada Jepang.
Pada 1943 bangunan stasiun yang hancur itu dibangun kembali oleh Rikuyu Sokyoku, badan yang bertanggungjawab atas transportasi darat di masa pendudukan Jepang. Rancangan bangunan itu dibuat oleh Ir. Thomas Nix (1904-1998), arsitek dan perencana kota dari Bandung. Sebelum kedatangn Jepang di Indonesia, pada 1938 Nix telah merancang gedung BPM-Shell di Jakarta dan Semarang yang sekarang menjadi kantor Pertamina. Selama perang, terpisah dari istri dan anak-anaknya yang ditahan di kamp lain, Nix ditugasi Rikuyu Sokyoku untuk merancang Stasiun Cilacap.
Rancangan Nix untuk Station Cilacap bergaya modernisme Nieuwe Bouwen. Bangunan ini seluruhnya menggunakan konstruksi beton bertulang. Tampak depannya didominasi sebuah menara dan sepuluh kolom yang menopang atap datar dari beton. Pintu masuk utama stasiun dinaungi kanopi. Overkapping lama masih digunakan, namun kemungkinan kolom-kolom lama dari besi diganti beton bertulang pada 1943, menyesuaikan dengan arsitektur bangunan stasiun yang baru.
