Stasiun ini memiliki 3 jalur, semua jalurnya dulu digunakan sebagai jalur trem angkutan penumpang dan barang. Sisa jalur lainnya digunakan sebagai sepur langsir gerbong barang dan sepur badug. Stasiun ini merupakan stasiun terakhir (terminus) di jalur kereta api Probolinggo-Paiton. Dulu, nama stasiun yang dipakai adalah Phaeton dengan singkatan stasiun PHT, namun diubah menjadi Paiton sesuai dengan ejaan bahasa Indonesia.
Stasiun ini merupakan stasiun yang dibangun oleh perusahaan kereta api swasta Hindia Belanda yaitu Probolinggo Stoomtram Maatschappij (PbSM) yang mendapat konsesi izin pembangunan jalur kereta api di area Probolinggo dan Kraksaan. Gedung dengan desain minimalis bergaya kolonial dibangun sekitar tahun 1912 seiring dioperasionalkannya lintas Gending Baroe-Paiton. Dulu juga terdapat pabrik gula Paiton yang terletak tidak jauh dari area stasiun, semua hasil gula disimpan di gudang stasiun sebelum diangkut ke pelabuhan.
