It is considered one of six of the "Great Kingdoms of Mindanao".
The balangay (large outrigger boats) that have been found along the east and west banks of the Libertad River (old Agusan River) have revealed much about Butuan's history. As a result, Butuan is considered to have been a major trading port in the Caraga region during the pre-colonial era
Originally a Hindu-following state, its last three rajahs, Soloy, Tunkin and Kalahap became Muslims with the arrival of Moro, Malay, Arab, Indian and Persian Islamic missionaries to the kingdom, which then converted many Butuanon natives to Islam. In 1521, the Spanish rulers encountered Rajah Kalahap, the ruling chieftain of the kingdom as well as his son Datu Kalaw. Like the neighboring Rajahnate of Bukidnon, Rajah Kalapah befriended the Spanish conquistadors and allowed Spanish and Filipino settlers, and Roman Catholic missionaries into his realm which he allowed to be a vassal state of the Spanish Empire.
However, in 1522 along with Rajah Aluy of the neighboring Rajahnate of Bukidnon, as well as Sultan Amirul-Umara of Sulu, Sultan Sharif Maka-Alang of Maguindanao, Sultan Saleh Tarik of Buluan and Sultan Yusuf of Lanao, signed a pact and formed an alliance with the effort of fighting the Spanish conquistadors in what is known as the Great War in Mindanao and Sulu. Rajah Kalahap was also joined by incoming Hindu migrants from Cebu, those Visayans who refused Roman Catholicism and Spanish rule.
However, the northern kingdoms of Mindanao, received the brunt of the Spanish attacks, and despite staging a valiant resistance, Rajah Kalapah and Rajah Aluy were both killed in battle. This caused the eventual downfall of both their kingdoms, and the retreating of the native warriors to the mountains.