Asal-usul nama "Sabah" dikatakan kurang jelas, dan terdapat banyak teori yang telah timbul. Salah satu contoh teori ialah ketika Sabah masih di bawah pemerintahan Kesultanan Brunei, ia dirujuk sebagai Saba kerana kehadiran pisang saba, nama sejenis pisang yang dinamakan 'pisang Saba' oleh masyarakat Bajau kerana pisang tersebut banyak sekali ditanam di sekitar pantai barat Sabah. Pisang ini juga dikenali sebagai 'pisang menurun' oleh masyarakat tempatan, namun begitu, terdapat perbezaan antara 'pisang Saba' dan pisang lain di sekitar Kepulauan Borneo. Disebabkan juga lokasi Sabah yang berhubung dengan Brunei, telah dikatakan bahawa Sabahialah perkataan Melayu Brunei yang bermaksud hulu[6] atau sebelah utara sungai.[7] Satu lagi teori mengatakan bahawa ia datang daripada Sabak, perkataan Melayu yang ertinya tempat di mana gula kabung diekstrak. Sabah juga merupakan perkataan Arab yang bermaksud matahari terbit. Kehadiran pelbagai teori ini menjadikan ia sukar untuk menentukan asal sebenar nama negeri ini.[8]

Sesetengah teori juga mengatakan bahawa Sabah pernah dirujuk sebagai Seludang dalam teks 1365 Jawa yang dikenali sebagai Nagarakretagama ditulis oleh Empu Prapañca.[9]