It is believed that the history of Muar started much earlier that the Sultanate of Malacca. There were many accounts recorded about the early history of Muar. In 1361, it was claimed that Muar was a part of the Majapahit empire. Another account also stated that Parameswara, upon his exile from Temasik before proceeding to found Melaka, had established a settlement at Kota Buruk, Pagoh, Ulu Muar. Muar is also the home for the one and only tomb of the 7th Malacca Sultanate, Sultan Alauddin Riayat Shah I (1477-1488). Muar witnessing the beginning of the Malacca Sultanate empire.
Historically, Muar was also where the deposed heir of the Malacca Sultanate (Sultan Mammud Shah) escaped to in 24th August 1511 following the invasion of the Portuguese, launched from Goa. During the Portuguese ‘s Afonso de Albuquerque invasion and attack in 1511, Muar played a role in resisting the Portuguese occupation of the Malacca; the Kubu Bentayan fort was built by the last Sultan of Malacca, and it is believed to be located at the present location of Bentayan Express Bus’s station (formely Pagoh Bus Stand) in Jalan Maharani, Muar. Sultan Mahmud to repel seaborne invasions, before he was defeated and retreat further to Kota Biawak Busuk and then to Kota Pagoh, this time witnessing the fall of the Malacca Sultanate empire. During the Portuguese occupation era, the Portuguese built a fortress named Fortaleza de Muar built in 1604 by Emanuel Godinho de Eredia in triangular shape to defend the colony against the attack of Dutch and Aceh instead at the same strategic site of Bentayan. The colonial British did just about the same thing at the Muar River site near Bentayan di defence against the advance of Japanese Imperial Army in the Battle of Muar in the 2nd World War.