Asal-usul perusahaan ini sangat tidak jelas. Dalam Encyclopaedie van Nederlandsch-Indië tercatat bahwa konsesi oleh Pemerintah Kolonial mengenai jalur Probolinggo–Kraksaan–Paiton sendiri telah dikeluarkan berdasarkan besluit tertanggal 15 Desember 1894 No. 6.[2]
Dengan berbekal konsesi tersebut, perusahaan ini membangun beberapa jalur kereta api dan trem yang dalam proses pembangunannya dibagi menjadi beberapa segmen sebagai berikut.[3]
Jalur kereta api Probolinggo–Paiton mulanya dari Pelabuhan Tanjung Tembaga Probolinggo lalu sejajar dengan jalur SS di petak Probolinggo–Jati. Di sinilah tempat lokomotif-lokomotif uap milik PbSM dirawat, karena diponya memang terletak satu kompleks dengan Stasiun Jati. Kraksaan–Kalibuntu hanya dijadikan sebagai lintas cabang pendukung Pelabuhan Kalibuntu.[2]
Perang Kemerdekaan menyebabkan lintas-lintas PbSM mangkrak dan sebagian di antaranya dicabut. Toer dkk. (1999) dengan merujuk pada Majalah Pantja Raja edisi 15 Juni 1946 mencatat bahwa jalur kereta api segmen Sebaung–Kraksaan dibangun kembali.[5] Akan tetapi, untuk segmen Probolinggo–Gending Baru masih belum dibangun sampai pertengahan dekade 1950-an begitu data dari ikhtisar laporan tahunan DKA.[6] Praktis, layanan kereta apinya juga tidak dapat dijalankan hingga 1960-an.
Pada tahun 1978, dalam Statistik Kotamadya Probolinggo 1980, sudah tidak ada lagi kereta api penumpang yang diberangkatkan dari Stasiun Jati karena jaraknya yang dekat dengan Stasiun Probolinggo.[7]
Armada
Untuk menunjang sistem, PbSM juga mendatangkan lokomotif yang perawatannya dipusatkan di Depo Lokomotif Jati. Berikut adalah tabel daftar armada lokomotif yang pernah dioperasikan oleh perusahaan ini.
_op_het_spooremplacement_te_Probolinggo_TMnr_10014037.jpg)
