Madura
Menurut versi cerita rakyat nama "Madura" berhubungan erat dengan cerita rakyat tentang Raden Adi Segara dan penyerangan Dampo Abang (raja dari Tiongkok) ke Madura.
Versi cerita rakyat pertama, nama Madura berasal dari kata maddhuna saghâra 'madunya laut'. Dari kata maddhuna saghâra ini, kemudian menjadi maddhuna dan akhirnya menjadi "Madura" seperti sekarang. Maddhuna saghâra adalah nama lain dari Raden Adi Segara putra Dewi Ratna Rara Agung. Dewi Ratna Rara Agung ini adalah putri Prabu Sangiangtunggal Maharaja Kraton Gilling Wesi di wilayah Medangkawulan. Konon karajaan ini berdiri sekitar 929 M di dekat Gunung Semeru dan Gunung Bromo.
Versi cerita rakyat kedua, nama Madura berasal dari kata maddhuna-dhârâ 'madu gadis'. Nama ini menurut cerita rakyat lahir dari ungkapan 'gadis Madura masih asli'. Artinya, 'madu masih utuh belum dihisap Dampo Abang', raja dari negeri Tiongkok yang ingin memperistri gadis-gadis Madura (menghisap 'madunya' gadis Madura). Gagalnya Dampo Abang memperistri gadis-gadis Madura tersebut karena kekalahan dalam peperangan dengan orang Madura.
Menurut versi ilmiah, nama Madura oleh beberapa akademisi dikaitkan dengan penghasilan Madura, kondisi geografis Madura, dan bahasa Sanskerta.
Versi ilmiah pertama, ditinjau dari segi penghasilan nama pulau Madura dapat disebut "madu dari laut". "Madu dari laut" ini dalam bahasa Jawa madu segara. Madu segara artinya 'madu dari laut', yakni garam. Dari kata inilah lalu muncul rangkaian kata Madura.
Versi ilmiah kedua, ditinjau dari segi geografis, nama pulau Madura ditafsirkan oleh masyarakat dari dua kata maddhu dan saghâra, yang artinya 'pojok lautan'. Tafsir ini dikaitkan dengan penduduk Madura yang secara geografis bertempat tinggal di pojok Pulau Jawa (Zainuddin dkk, 1978).
Versi ilmiah ketiga, ditinjau dari segi bahasa, nama Madura dapat dikaitkan dengan bahasa Sanskerta (Sanskrit). Kata Madura dalam bahasa Sanskerta artinya 'manis' dan 'cantik'.
Secara historis, nama Madura bisa saja berkaitan dengan datangnya saudagar Muslim dari Gujarat ke Nusantara (termasuk Madura) pada abad ke-13 M, era Kesultanan Demak. Pembuktiannya terlihat pada peta kuno Madura, dimana di sepanjang pesisir utara pulau Madura terdapat pelabuhan. Pelabuhan ini menjadi tempat pertemuan antara saudagar Gujarat dengan masyarakat lokal.
Kangean
Nama "Kangean" diturunkan dari istilah 'ꦏꦲꦾꦁꦲꦤ꧀' (Ka-hyang-an) dalam bahasa Jawa Kuno yang merujuk kepada sistem kepercayaan kuno masyarakat Nusantara yang percaya kepada entitas Hyang sebagai sumber pemujaan, akar kata Ka-hyang-an ini juga juga dikenali secara lokal oleh penduduk Kangean sebagai "𑻠𑻢𑻬𑻨" atau "ᨀᨂᨐᨚ" (Kangayan), yang kemudian juga dikekalkan sebagai salah satu nama kecamatan di Pulau Kangean. Hal ini berkaitan dengan pengaruh Bali yang diperkirakan memiliki andil dalam memberikan pengaruh budaya dan kepercayaannya, Bali yang disebut sebagai "Pulau Dewata" (pulau para Dewa) secara geografis berada di selatan Pulau Kangean (ᬓᬳ᭄ᬬᬂᬳᬦ᭄, Kahyangan) yang dipercayai oleh masyarakat Bali sebagai pulaunya para Dewata (ᬤᬾᬯᬢᬵ, Dewatā) bersemayam.
Dalam teori lain, nama "Kangean" diperkirakan berakar dari kata 江 (Jiāng) dalam bahasa Mandarin Kuno, yang mana kata ini tersusun dari gabungan akar kata 水 (Shuǐ) dan 工 (Gōng) yang bermakna 'air' dan 'kerja' secara harafiah, merujuk kepada masyarakat suku Kangean yang rata-rata bermata pencahariannya berhubungan dengan laut.