The original inhabitants of Malaybalay come from the seashores of Northern Mindanao (Misamis Oriental area) but were driven towards the mountains because of pirates and the arrival of Spanish colonizers. Before the final conquest of the central part of Mindanao (Bukidnon area), Sumilao, Linabo, Mailag and Silae has been established by Spanish missionaries (Dominicans and Jesuits). In 1850, Kalasungay (an old settlement site in Malaybalay), was burned down by the Spaniards during their final battle with the lumads, in which all male adults were killed and the women and children were taken as hostages. This battle is the last recorded resistance by the original inhabitants against the Spanish conquerors.
A few years after their defeat, the survivors of the said battle who fled to Silae slowly returned to the area ans established a new settlement near the Sacub River (present-day Rizal Park) under the protection of Datu Mampaalong. Together with thirty (30) other datus, Datu Mampaalong accepted Spanish dominion and embraced Christianity on June 15, 1877, ending the long standing war between them. On that day, the Spaniards made Malaybalay into a pueblo named Oroquita del Interior with a territory covering the area of what is now the province of Bukidnon, but the name of the settlement was still retained as Malaybalay.
From 1877 until the coming of the Americans, covering a span of 20 years, Capitanes, who were acknowledge tribal chieftains and were appointed by the Spaniard missionaries, governed Malaybalay. Some of this leaders were Mariano Melendez (Datu Mampaalong), Doroteo Melendez, Juan Carbajal, Alejandro Bontao, Esteban Tilanduca and Faustino Abello
In 1850, Malaybalay became a part of the province of Misamis Oriental as a municipal district. The Philippine Commission then headed by Commissioner Dean C. Worcester, Secretary of Interior and a member of the Philippine Commission proposed the separation of Bukidnon from Misamis Oriental Province.
On August 20, 1907, the Philippine Commission Act No. 1693 was enacted creating the Province of Agusan and the sub-province of Bukidnon. Malaybalay was then formally created as a municipality on October 19, 1907. When Bukidnon was declared as a regular province and become an independent political unit on March 10, 1917 by virtue of the creation of the Department of Mindanao and Sulu under Act 2711, Malaybalay was designated as its provincial capital.
During the Second World War, in 1942, the Japanese occupation troops entered Bukidnon. They occupied Malaybalay, establishing a camp in Casisang. Guerrilla groups operating around Malaybalay made frequent raids on the Japanese camps from the time of the occupation until the arrival of the Americans. In 1945, American liberation forces, together with the Philippine Commonwealth Forces and Filipino guerrillas liberated Malaybalay.
On March 26, 1996, the Sangguniang Bayan of the municipality of Malaybalay passed Resolution No. 3699-96 petitioning to the House of Representatives for the conversion of Malaybalay into a city. Reginaldo Tilanduca, 2nd District Representative of Bukidnon at that time, files House Bill No. 6275, proposing the creation of Malaybalay into a component city. On February 11, 1998, President Fidel Ramos signed the act (R.A. 8490) that converted Malaybalay to a city, making it the first component city of Bukidnon.