Mutiara merupakan layanan kereta api penumpang milik Perusahaan Negara Kereta Api (PNKA) yang pernah melayani rute Surabaya–Jakarta via Semarang. Kereta api ini diluncurkan pada 26 September 1971. Di awal era peluncurannya, menggunakan layanan KA kelas I yang hanya membawa kereta kelas satu dan kereta makan. Dalam iklan yang dimuat dalam Berita Buana edisi 25 September 1971, PNKA menawarkan fasilitas AC dan hiburan audio dan menggunakan kursi yang dapat direbahkan (reclining seat) dan pelayanan makan pagi, makan malam, dan makanan ringan.^[3]

Belakangan, nama kereta api ini diubah menjadi Mutiara Utara, karena munculnya kereta api Mutiara Selatan. Pada pertengahan dekade 1980-an, Mutiara Utara diubah menjadi kelas I dan II. Pada tanggal 9 Juni 1990, Perusahaan Jawatan Kereta Api (PJKA) meresmikan kereta kelas eksekutif (saat itu merupakan kelas di atas kelas I eksisting), ditambahkan untuk KA Bima dan Mutiara Utara. Anwar Suprijadi, yang saat itu menjadi Direktur Operasional PJKA, menargetkan pendapatan sebesar Rp6 miliar dari penjualan tiket kelas eksekutif.^[4]

Pada tanggal 11 Maret 1992, Perumka mengubah format kelas kereta api eksekutif, menjadi Eksekutif-A dan Eksekutif-B,^[5] yang kelak disederhanakan menjadi "Eksekutif" saja. Mutiara Utara sempat dihilangkan sejenak saat Perumka meluncurkan Suryajaya pada tahun 1994. Namun, Mutiara Utara dimunculkan kembali oleh Perumka. Tidak bertahan lama, layanan Mutiara Utara pun berakhir pada bulan Oktober 1995 dan digantikan oleh Sembrani dengan kelas Eksekutif Satwa.

Kereta api Sembrani dioperasikan pertama kali pada tanggal 16 Oktober 1995 oleh Perusahaan Umum Kereta Api (Perumka) sebagai pembaruan dan pengembangan dari layanan kereta api Mutiara Utara yang telah beroperasi sebelumnya. Di awal-awal operasinya, Kepala Seksi Niaga Perumka Daerah Operasi VIII Surabaya menargetkan penumpang harian sebesar 4.000/hari. ^[6]

Pada dekade 2000-an, kereta api ini sempat dikenal buruk oleh masyarakat karena ketidaknyamanan kursi penumpang pada beberapa rangkaian kereta buatan 1950–1960-an. Untuk memperbaiki citra kereta api ini, satu rangkaian kereta api tersebut dilakukan penyehatan di Balai Yasa Manggarai yang mulai dioperasikan pada tahun 2010 dengan sebutan "Sembrani New Image".^[7] Per tahun 2016, kereta api Sembrani beroperasi menggunakan rangkaian kereta eksekutif buatan PT INKA keluaran 2016.

Per pertengahan bulan November 2019 sebelum dimulai dengan pemberlakuan grafik perjalanan kereta api (Gapeka 2019), kereta api Sembrani (bersamaan dengan kereta api Gumarang) ini diambil alih kepemilikan operasional ke Daerah Operasi VIII Surabaya dari Daerah Operasi I Jakarta beserta rangkaian kereta pun dimutasi ke Depo Kereta Surabaya Pasarturi (SBI), yang disebabkan dua kereta baru yang akan datang di Gapeka 2019, yakni Dharmawangsa (PSE-SBI) dan Anjasmoro (PSE-JG) serta diperpanjangnya tiga layanan kereta api dari Daerah Operasi II Bandung yaitu Argo Wilis (GMR-BD-SGU), Mutiara Selatan (GMR-BD-ML) dan Malabar (ML-BD-PSE) per tanggal 1 Desember 2019. Sejak 1 Desember 2019, kereta api Sembrani menambahkan layanan kereta kelas Luxury sebanyak 26 tempat duduk yang sebelumnya dipakai oleh Taksaka.

Kereta api Sembrani mulai melayani penumpang di Stasiun Ngrombo per 20 Januari 2020.^[8] Pada tanggal28 September 2022, kecepatan KA Sembrani (kecuali Sembrani Tambahan) ditingkatkan menjadi 120 km/jam dari semula hanya 105—110 km/jam.^[9] Kereta api Sembrani Tambahan menambah pemberhentian di Stasiun Cikarang. Mulai tanggal 1 Februari 2022, kemudian pada masa angkutan Hari Raya Idulfitri 2023 juga menyusul ditingkatkan kecepatannya menjadi 120 km/jam.

Per 1 Juni 2023 bertepatan dengan pemberlakuan Gapeka 2023, Kereta api Sembrani akan menambahkan layanan perjalanan pagi dengan nomor KA 61-62 merupakan penerus dari Kereta api Sembrani Tambahan yang berangkat dengan jadwal pagi dari Surabaya Pasarturi maupun Gambir. Kereta ini merupakan uji coba pelayanan kereta penumpang di pagi hari pada arus mudik dan balik Hari Raya Idulfitri 1444 H.^[10] Sehubungan dengan perubahan rangkaian kereta api Argo Bromo Anggrek menjadi eksekutif generasi baru, mulai 29 Maret 2024, kereta api Sembrani akan menggunakan rangkaian kereta api lungsuran dari rangkaian baja nirkarat generasi pertama.^[11]

Mulai tanggal 1 Juni 2025, kereta api Sembrani (dengan No KA 40-41) akan melayani kelas Luxury Sleeper (lungsuran dari Kereta api Argo Bromo Anggrek) yang sekaligus menggantikan peran kelas Luxury Generasi 2.