The origins of the word Melayu ('Malay') are disputed. One theory suggests that it is derived from the Javanese terms melayu or mlayu (to steadily accelerate or to run), to describe the strong current of a river in Sumatra that today bears the name Sungai Melayu ('Melayu river'). The name was later possibly adopted by the Melayu Kingdom, as it is common for people in the region to be known by the name of the river on which they settled.
Another theory hold that it originates from the Tamil words Malai and ur meaning "mountain" and "city, land", respectively.
An early literary appearance was in Vayu Purana where the word "Malaya Dvipa" (literally "mountainous dvipa") was mentioned, referring to the mountainous terrain of Malay Peninsula. Then, the term "Maleu-Kolon" was used in Geographia by Ptolemy which is believed to have originated from the Sanskrit term malayakolam or malaikurram, referring to a geographical part of Malay Peninsula.
In 7th century, the first use of the term for a nation or a kingdom was recorded by Yijing.
The East Javanese Anjukladang inscription dated from 937 CE Medang Kingdom stated the Sima status is awarded to Anjukladang village and a jayastambha (victory monument), which later upgraded as a temple, was erected in recognition of their service on repelling the invading forces from Malayu. The temple mentioned here is probably the Candi Lor made of bricks which is now in ruins, located in Candirejo village in Nganjuk Regency. The mentioning of invading Malayu forces refer to the old name of Sumatran Malayu Kingdom, which probably refer to Srivijaya instead. This means by the 10th century, the Javanese identify their Sumatran-based enemy as "Malayu".
An inscription on the south wall of the 11th century Brihadeeswarar Temple also made a reference to Malaiyur, a kingdom that had "a strong mountain for its rampart" in Malay Peninsula that fell to the Chola invaders during Rajendra Chola I's campaign.
In the later Yuan Dynasty (1271–1368) and Ming Dynasty (1368–1644), the word Ma-La-Yu was mentioned often in Chinese historical texts - with changes in spelling due to the time span between the dynasties - to refer to a nation near the southern sea. Among the terms used was "Bok-la-yu", "Mok-la-yu" (木剌由), Ma-li-yu-er (麻里予兒), Oo-lai-yu (巫来由) - traced from the written source of monk Xuanzang), and Wu-lai-yu (無来由). In the chronicle of Yuan Dynasty, the word "Ma-li-yu-er" was mentioned in describing the Sukhothai Kingdom's southward expansion against Malay states of the peninsula.:
- "..Animosity occurred between Siam and Ma-li-yu-er with both killing each other..."
In response to the Sukhothai's move, a Chinese envoy arrived at the Ram Khamhaeng's court in 1295 bearing an imperial order: "Keep your promise and do no evil to Ma-li-yu-er". This nation of "Ma-li-yu-er" that appeared in the Chinese record possibly a similar nation that was mentioned by the famous Venetian traveller Marco Polo (1254–1324) who lived during the same period. In Travels of Marco Polo, he made a reference to a kingdom named "Malauir" in the Malay peninsula. The Khmer recorded the nation of Melayu, however, its progeny Srivijaya, was also called Melayu.
According to the translation by Slamet Muljana, the word bhūmi Mālayu (literally "Land of Malayu") is inscribed on the Padang Roco Inscription, dated 1286 CE, according to the inscription, bhūmi Mālayu is associated with the Dharmasraya kingdom. On the Amoghapasa inscription, dated 1347 CE, the word Malayapura (literally "city of Malaya" or "kingdom of Malaya") was proclaimed by Adityawarman, again referring to Dharmasraya. The word "Melayu" is also mentioned in the Malay annals referring to a river in Sumatra:
- "...Here now is the story of a city called Palembang in the land of Andelas. It was ruled by Demang Lebar Daun, a descendant of Raja Shulan, and its river was the Muara Tatang. In the upper reaches of the Muara Tatang was a river called Melayu, and on that river was a hill called Si-Guntang Mahameru..."