Before the founding of the Sultanate of Maguindanao, according to the Yuan Dynaty annals, Nanhai Zhi (At year 1304), a polity known as Wenduling 文杜陵 was its predecessor-state. This Wenduling was invaded by then Hindu Brunei, called Pon-i (present-day Sultanate of Brunei), until it rebelled against Pon-i after the Majapahit Empire's invasion of Pon-i. Islamization then happened afterwards. Firstly, two brothers named Mamalu and Tabunaway lived peacefully in the Cotabato Valley on Mindanao and then Shariff Mohammed Kabungsuwan of Johor in what is now modern day Malaysia, preached Islam in the area in the 16th century, Tabunaway converted, while Mamalu decided to hold fast to their ancestral animist beliefs. The brothers parted ways, with Tabunaway heading to the lowlands and Mamalu to the mountains, but they vowed to honor their kinship, and thus an unwritten pact of peace between Muslims and the indigenous peoples was forged through the two brothers.

As Shariff Kabungsuwan introduced Islam in the area, which was earlier Hindu-influenced from Srivijaya times, at the end of the 16th century and established himself as Sultan seated in Malabang-Lanao. The Maguindanao Sultanate also had a close alliance with the Ternate Sultanate, a sultanate in the Moluccas region of Indonesia. Ternate regularly sent military reinforcements to Maguindanao during the Spanish-Moro Wars.

During the Spanish colonial period, the Sultanate of Maguindanao was able to defend its territory, preventing the Spaniards from colonising the entire Mindanao and ceding the island of Palawan to the Spanish government in 1705. The island priory ceded to him by Sulu Sultan Sahabuddin. This was to have help dissuaded Spanish encroachments into the island of Maguindanao and Sulu itself. Chinese gongs, yellow as a color of royalty, and idioms of Chinese origin entered Mindanao culture. Royalty was connected to yellow. The color yellow was used by the Sultan in Mindanao. Chinese tableware and gongs were exported to the Moros.