The original inhabitants of Malaybalay were said to have come from the seashores of Northern Mindanao but were driven inward by marauding pirates and the colonizing Spaniards. Before the final conquest of the hinterlands of Mindanao, Malaybalay together with Sumilao, Linabo, Mailag and Silae had been known settlements in Bukidnon. In 1850 the entire village of what is now Kalasungay (an old settlement site of Malaybalay) was burned down during the battle against the Spaniards. All male adults were killed on sight. All women and children were taken hostage. It was the last recorded resistance by the inhabitants against the conquering Castillan Army.

A few years later, those who survived and fled to Silae slowly came back and settled near the Sacub River (what is now the Rizal Park) under the protection of Datu Mampaalong. This leader led 30 other datus on June 15, 1877 to accept Spanish dominion and embrace Christianity, 356 years after Spain first discovered the Philippines. On that day of 1877, Malaybalay became a pueblo with the name “Oroquita del Interior” with a territory covering the land area of what is now the entire province of Bukidnon. But the original name of Malaybalay remained. From 1877 until the end of the Spanish rule in the islands, which covered a period of 20 years, Capitanes who were appointed from among the acknowledged tribal chieftains governed Malaybalay. They were Mariano Melendez (Datu Mampaalong), Doroteo Melendez, Juan Carbajal, Alejandro Bontao, Esteban Tilanduca and Faustino Abello.