Kawasan ini pertama kali dikenali sebagai penduduk utara Siam sebagai Gangganu atau Ganggayu (Treasury of Permata) kerana banyaknya batu permata di dekat Sungai Johor. Peniaga Arab merujuknya sebagai جوهر (jauhar), perkataan yang dipinjam dari Parsi گوهر (gauhar), yang juga bermaksud "batu permata" atau "permata". Apabila orang tempatan mendapati sukar untuk menyebut perkataan Arab dalam dialek tempatan, nama itu kemudiannya menjadi Johor. Sementara itu, kelompok Jawa Lama Nagarakretagama menamakannya sebagai kawasan Ujong Medini (akhir tanah) kerana ia adalah titik paling selatan di daratan Asia. Nama lain melalui penulis Portugis, Manuel Godinho de Erédia, merujuk kepada pelayaran Marco Polo ke Ujong Tanah (akhir tanah Semenanjung Tanah Melayu) pada tahun 1292. Kedua-dua Ujong Medini dan Ujong Tanah telah disebutkan sejak sebelum penubuhan Kesultanan Melaka. Sepanjang tempoh tersebut, beberapa nama lain juga wujud seperti Galoh, Lenggiu dan Wurawari. Johor juga dikenali dengan penghormatan Arabnya sebagai دارالتعظيم (Darul Ta'zim) atau "Abode of Dignity" serta terjemahannya iaitu tempat perlindungan yang bermaruah.