Terdapat banyak sekali teori mengenai asal usul perkataan Melayu. Salah satu teori mencadangkan bahawa ia diterbitkan daripada istilah bahasa Jawa, melayu atau mlayu yang bermaksud memecut sentiasa atau mengalir, bagi menggambarkan aliran kuat di sebuah sungai di Sumatra. Sungai tersebut kini dikenali dengan nama Sungai Melayu yang merupakan cawangan sebelah kanan yang menuju ke ulu Sungai Batanghari dan tadahannya itu mencecah Pagar Ruyung. Nama sungai ini kemungkinannya telah diambil oleh Kerajaan Melayu bagi menamakan kerajaannya kerana sudah menjadi kebiasaan penduduk di rantau itu dikenali dengan nama sungai yang menyaliri kawasan penempatan mereka.
Teori lain pula berpegang bahawa kata "Melayu" ini berasal dari perkataan berbahasa Sanskrit "Malaya" yang bermaksud pergunungan atau gua dan perkataan berbahasa Tamil iaitu "Ur" yang bermaksud kota atau tanah. Teori ini mungkin merujuk kepada Banjaran Barisan di Sumatra.
Kemunculan perkataan ini dalam sastera terawal sekali boleh didapati dalam bab ke-48, Vayu Purana, yang menyebut "Malayadvipa" yang bermaksud pulau yang bergunung ganang serta menggambarkannya sebagai salah satu daripada wilayah di lautan timur dipenuhi oleh emas dan perak.
Sesetengah cendekiawan menyamakan istilah "Malayadvipa" ini dengan Sumatra, namun beberapa cendekiawan India percaya bahawa istilah itu boleh juga merujuk kepada Semenanjung Tanah Melayu yang juga mempunyai kawasan pergunungan di sepanjang semenanjung itu, dikenali sebagai Banjaran Titiwangsa. Kawasan banjaran ini dikenali sebagai kawasan yang kaya dengan galian mineral emas, yang sepadan dengan gambaran pada istilah Malaydvipa dalam Vayu Purana itu.
Seterusnya, istilah "Maleu-Kolon" yang digunakan oleh Ptolemy dalam karya beliau berjudul Geographia dipercayai berasal dari istilah bahasa Tamil iaitu Malayakolam atau Malaikurram, merujuk kepada bahagian geografi semenanjung itu. Pada abad ke-7 masihi, penggunaan awal istilah "Melayu" ini bagi merujuk satu bangsa atau kerajaan mula dicatatkan oleh Yijing.
Prasasti Anjuklang di Jawa Timur bertarikh 937 masihi dari zaman Mataram menjelaskan bahawa taraf Sima telah dianugerahkan kepada Kampung Anjukladang dan satu jayastambha atau tugu kejayaan yang kemudiannya dinaik taraf menjadi pecandian, dipacakkan bagi menghargai jasa baik penduduk kampung itu yang menangkis serangan tentera dari Kerajaan Melayu. Candi yang disebutkan di sini berkemungkinan adalah Candi Lor yang diperbuat daripada batu bata (kini telah menjadi runtuhan) terletak di Kampung Candirejo di Kabupaten Nganjuk. Sebutan mengenai tentera Melayu yang menakluki itu merujuk kepada istilah lama "Kerajaan Melayu dari Sumatra" yang berkemungkinan juga membawa maksud Srivijaya. Hal ini bermaksud, orang Jawa mengenalpasti musuh mereka yang bertapak di Sumatra pada abad ke-10 masihi itu sebagai "Malayu" atau sekurang-kurangnya, "tentera Melayu dari Srivijaya."
Satu lagi prasasti di tembok selatan Kuil Sri Brihadeeswarar pada abad ke-11 masihi juga membuat rujukan kepada Malaiyur, sebuah kerajaan yang mempunyai "gunung yang tinggi sebagai benteng" semasa penaklukan dinasti Chola ke atas Srivijaya. Keadaan ini merujuk kepada penakluk dari Chola semasa kempen peperangan Raja Rajendra Chola I di Selat Melaka.
Semasa Dinasti Yuan (1271 - 1368) dan Dinasti Ming (1368 - 1644), perkataan Malayu disebut selalu dalam teks sejarah China dengan perbezaan ejaan disebabkan oleh sela masa antara dinasti bagi merujuk kepada satu bangsa di lautan selatan. Antara istilah yang digunakan adalah:
- 木剌由 Mok-la-yu
- 麻里予兒 Ma-li-yu-er
- 巫来由 Oo-lai-yu yang dikesan dari sumber tulisan Xuanzang, seorang bhiksu Buddha
- 無来由 Wu-lai-yu
Dalam babad Dinasti Yuan, perkataan "Maliyuer" disebut bagi menjelaskan peluasan kuasa Kerajaan Sukhothai ke kawasan Malayu:
"...Perseteruan berlaku antara Siam dan Ma-li-yu-er apabila mereka berbunuh semasa sendiri..."
Sebagai tindak balas daripada tindakan Sukhothai itu, rajaduta China tiba di istana Raja Ramakhamhaeng pada tahun 1295 membawa perintah maharaja, "Tepati janjimu dan dilarang berbuat kejahatan kepada Ma-li-yu-er". Bangsa "Ma-li-yu-er" yang muncul dalam rekod China ini boleh jadi juga adalah bangsa yang disebut oleh pengembara Venice bernama Marco Polo (1254 - 1324) yang hidup pada zaman itu. Dalam The Travels of Marco Polo, beliau membuat rujukan kepada satu kerajaan yang dinamakan sebagai "Malauir" di Semenanjung Tanah Melayu.
Perkataan bhūmi Mālayu yang bermaksud Tanah Melayu direkodkan dalam Prasasti Padang Roco yang bertarikh 1286 masihi. Menurut prasasti tersebut, bhūmi Mālayu dikaitkan dengan Dharmasraya. Dalam Prasasti Amoghapasa bertarikh 1347, perkataan Malayapura yang bermaksud Kota Melayu atau Kerajaan Melayu diisytiharkan oleh Raja Adityavarman bagi merujuk kepada Dharmasraya. Perkataan Melayu ini disebut dalam babad-babad Melayu sebagai merujuk kepada sebatang sungai di Sumatra:
"...Di sinilah kini satu kisah dari kota bergelar Palembang di tanah Andelas. Ia diperintah oleh Demang Lebar Daun, keturunan Raja Chulan, dan sungainya di Muara Tatang. Ulu kerajaannya di Muara Tatang itu bertemu dengan Sungai Melayu, dan di situlah berdirinya gunung yang dipanggil, Si Guntang Mahameru..." - CC Brown
"...Terdapat satu negeri di tanah Andalas bernama Paralembang, yang kini dinamakan sebagai Palembang, rajanya pula bernama Daman Lebar Dawn, yang berasal usul dari Raja Chulan, yang mana dia adalah cicitnya. Nama sungainya adalah Muara Tatang, di mana jatuh pula satu lagi sungai bernama Sungai Malayu padanya, berdekatan dengan punca di sebuah gunung iaitu Gunung Sagantang Maha Miru..." - J. Leyden
Untuk beberapa lamanya, Kerajaan Melayu dikenal pasti oleh orang Cina sebagai pengganti kepada Srivijaya. Seperti yang dinyatakan apabila rajaduta Sanfoqi ke benua China pada tahun 1028 masihi, ia sebenarnya merujuk kepada Kerajaan Malayu di Jambi. Bukannya merujuk kepada Kerajaan Srivijaya di Palembang. Tiada rajaduta dari Sanfoqi dihantar ke China antara tahun 1028 hingga tahun 1077 masihi. Hal ini menunjukkan bahawa mandala Srivijaya telah pun pudar. Berkemungkinan Srivijaya telah hancur pada tahun 1025 masihi.
Pada abad berikutnya, catitan sejarah Cina masih lagi membuat rujukan kepada Sanfoqi, namun istilah ini kemungkinannya merujuk kepada Kerajaan Malayu di Jambi. Bukti epigrafi terakhir yang menyebut nama Srivijaya didapati dalam Prasasti Tanjore oleh Kerajaan Chola pada tahun 1030 atau 1031 masihi.
