Bahasa Rojak boleh dikesan seawal zaman Kesultanan Melayu Melaka apabila satu entrepot antarabangsa didirikan oleh Parameswara pada tahun 1402 di Melaka dan pelabuhan ini menarik ramai pedagang yang secara keseluruhannya bertutur lebih 80 bahasa daripada pelbagai bangsa dan budaya. Pedagang dunia dan penduduk yang mengguna pakai pelbagai bahasa dalam satu perbualan amat biasa berlaku. Mengikut kata-kata Ensiklopedia Malaysia (vol. Bahasa dan Budaya), keadaan ini merupakan sebahagian daripada pijin bahasa penghubung yang dikenali sebagai Bahasa Rojak di Malaysia. Keunikan bahasa ini terdapat dalam gaya alihannya, seseorang mungkin memulai perbualan dalam bahasa Melayu dan kemudian menyambung dengan bahasa Inggeris, dan seterusnya mencampurkan satu atau dua perkataan bahasa Kantonis dan bahasa Tamil dan menamatkannya dengan istilah bahasa Mandarin atau bahasa Jepun. Semasa pemerintahan Parameswara apabila dua kumpulan pedagang tanpa satu bahasa kongsian, mereka akan cuba untuk bertutur dalam apa jua bahasa untuk mendapat keputusan yang terbaik dalam memahami antara satu sama lain dan hasilnya mungkin suatu pijin atau Rojak. Untuk memahami asal-usul Bahasa Rojak Malaysia, seseorang mungkin perlu membaca sejarah Malaysia terutama Melaka sewaktu Parameswara. Dalam awal 1500-an, pelawat Portugis Tome Pires menjumpai di Melaka "mur dari Kaherah, Makkah, Aden, Abyssinia, Malindi, Ormuz, Parsees, Rumes, Turks, Turkomans, orang Kristian Armenia, Gujaratee, lelaki Chaul, Dabhol, Goa, dari negara Deccan, Malabar dan Kling, pedagang Orissa, Ceylon, Bengal, Arakan, Pegu, Siam, lelaki Kedah, Melayu, lelaki Pahang, Patani, Kemboja, Champa, Cochin China, Cina, Lequeos, lelaki Brunei, Lucoes, lelaki Tamjompura, Laue, Banka, Linga, Moluccas, Banda, Bima, Timor, Madura, Java, Sunda, Palembang, Jambi, Tongkal, Indragiri, Kappatta, Menangkabau, Siak, Arqua (Arcat?), Aru, Bata, negara Tomjano, Pase, Pedir, Maldives...". Orang-orang ini datang ke Melaka dengan kapal dan pangjava. Menjelang 1511, Melaka mempunyai jumlah penduduk 50,000 termasuk komuniti pedagang yang bertutur 84 bahasa.