Berdirinya RSUD Provinsi NTB berawal dari bangunan gedung yang digunakan sebagai rumah sakit berasal dari perubahan gedung peninggalan Belanda yang didirikan sekitar tahun 1915, terletak di tengah Kota Mataram diatas tanah seluas 1,25 hektar yang awalnya merupakan gedung sekolah dasar (HIS). Pada jaman penjajahan jepang digunakan sebagai tempat pendidikan sekolah menengah Tji Gako dan sekolah guru (KYO IN dan SI HANG GAKO). Setelah Indonesia merdeka tidak lagi sebagai tempat pendidikan tetapi sebagai tempat Palang Merah Indonesia kemudian menjadi rumah sakit dengan nama Rumah Sakit Beatrix. Antara tahun 1947-1948 baru berganti nama menjadi Rumah Sakit Umum Mataram dan menjadi bagian dari Dinas Kesehatan Rakyat Daerah Lombok. Pada masa itu bangunan gedung ditambah lagi sesuai dengan kebutuhan. Pada tahun 1959 Daerah Nusa Tenggara Barat dibagi menjadi Kabupaten (Daerah Swatantra Tingkat II). Rumah Sakit menjadi milik Daerah Lombok Barat.
Surat Keputusan Gubernur Kepala Daerah Tingkat I Nusa Tenggara Barat No.448/Pem.47/5/151 tanggal 5 November 1969 mengubah status Rumah Sakit Umum Mataram yang dikelola Pemerintah Kabupaten Lombok Barat menjadi milik dan dikelola Pemerintah Daerah Provinsi Nusa Tenggara Barat dan disebut Rumah sakit Sakit Umum Provinsi Nusa Tenggara Barat. Tahun 2005 RSU Mataram berubah tipe dari tipe B menjadi tipe B Pendidikan sesuai SK Menkes No.13/Menkes/SK/1/2006 RSU Mataram menjadi RSUD Mataram.
Ditahun 2007 telah dimulai peletakan batu pertama pembangunan relokasi RSUP NTB secara bertahap di Kelurahan Dasan Cermen Kota Mataram dengan luas area 122.416 m2 dengan kapasitas tempat tidur 500 tempat tidur. Total tempat tidur nantinya akan menjadi 786 tempat tidur. Pada saat yang sama dicanangkan oleh Gubernur bahwa RSUP NTB yang lama akan menjadi Rumah Sakit khusus ibu dan anak dibawah kestauan RSUP NTB.
Tahun 1976 dr. Abdul Majid, Sp.B adalah dokter bedah pertama di RSUD Provinsi Nusa Tenggara Barat, yang waktu itu satu-satunya rumah sakit pemerintah di Provinsi Nusa Tenggara Bara. Beliau berasal dari Kota Surabaya. Selama kurang lebih 5 tahun mengabdi, pada tahun 1981, dr. Abdul Majid, Sp.B digantikan oleh dr. Santyo W. Sp.B sebagai dokter bedah umum di Provinsi Nusa Tenggara Barat. Selama kurun waktu tersebut, sebagian besar kasus bedah ditangani oleh beliau, karena belum ada ahli bedah bagian lain.
Sejak berubah nama menjadi Rumah Sakit Umum Daerah Provinsi NTB pada tahun 1969, sarana ruang operasi yang ada waktu itu hanya 4 ruangan, yaitu Bedah Umum, Obgyn, THT, dan Mata. Untuk sumber daya dokter anestesi belum ada, tindakan operasi dibantu oleh perawat yang dilatih khusus. Metode anestesi masih menggunakan chloretyl dengan tehnik open drop. Baru sekitar tahun 1989 dokter anestesi pertama datang yaitu dr. Sulasno, Sp. An. Pada pertengahan tahun 1988 mulai bertambah tenaga dokter bedah lainnya, seperti dr. IGB Budhiarta, Sp.B, dr. Sigit Jatmika (1999) sampai sekarang ini. Seiring dengan meningkatnya pelayanan, mulai tahun 1995, RSUD Provinsi NTB membuka poli bedah orthopedi oleh dr. Inu, Sp.OT dilanjutkan bedah urologi tahun 2009 oleh dr. Suharjendro, Sp.U, bedah saraf tahun 2011 oleh dr. Bambang, Sp.BS, sehingga bedah umum merupakan pionir dan cikal bakal terbentuknya subdivisi bedah lainnya.
Salah satu kegiatan bedah terbesar yang pernah dilakukan adalah bakti sosial (baksos) operasi bibir sumbing di Kota Bima tahun 1990. Untuk kegiatan-kegiatan ilmiah masih bersifat lokal karena terbatasnya sumber daya waktu itu.
Program Studi Pendidikan Dokter berdiri pada tahun 2003 dibawah binaan Fakultas Kedokteran Universitas Udayana. Fakultas kedokteran Unram menjadi fakultas dan mandiri sejak tahun 2007 dan menggunakan Kurikulum berbasis kompetensi sejak 2007. Pada tahun 2017, Program studi pendidikan dokter dan program studi profesi dokter mandapatkan akreditasi A dari LAMPT-Kes. Spesifikasi dan kompetensi lulusan yang dihasilkan minimal sesuai dengan standar kompetensi dokter Indonesia dan standar pendidikan dokter Indonesia.