Rajah Siawi and Rajah Kulambo, members of the nobility of the Surigaonon and Butuanon people, respectively, were encountered by the Magellan expedition in 1521 on the island of Limasawa (which was a hunting ground for the rulers). Antonio Pigafetta describes them as being tattooed and covered in gold ornaments, an indication that they are allies of the pintados of the Lakanate of Lawan. Pigafetta also records the name of the Surigao region as "Calagan".

The explorer Ruy López de Villalobos headed an expedition to Surigao in 1543, an attempt at subjugation which failed because of the resistance of the natives. At that time the island of Mindanao was given the name Caesarea Caroli, in honor of Carlos I of Spain. Jesuit missionaries visited Butuan in 1597 but did not make much progress in Christianizing the people. It was not until 1609, when a full-dress expedition was launched, that Spanish authority was imposed to Tandag. In 1622, the arrival of the Recollect missionaries in Tandag commenced the establishment of permanent mission in Surigao.

The area of Surigao was once part of an ancient district referred to as "Caraga" during the Spanish colonial period named after its chief inhabitants, the Caraga tribe or Caragans who were largely concentrated in a settlement called Caraga. The ancient district of Caraga was created in 1609. The seat of government was at Tandag until it was transferred to the town of Surigao in 1848.

Six Spanish military districts were established in Mindanao in 1860 and the areas of present-day Surigao del Norte, Surigao del Sur, Dinagat Islands, Agusan del Norte and Agusan del Sur (collectively called Agusan back then), Davao del Norte, Davao de Oro, Davao Oriental, including the territory lying between present day Butuan and Caraga bays, formed the third district called the "East District" which was changed in 1870 to "Distrito de Surigao". By the end of the Spanish rule in 1897, Agusan had been organized as a single politico-military comandancia named "Butuan", within the administrative jurisdiction of District of Surigao.

District of Surigao became a chartered province on May 15, 1901 (Philippine Commission Act 127). The territorial expanse of the Surigao province was further reduced in 1907 when the politico-military commandancia of Butuan, was created into a separate province and officially named it Agusan with present-day Butuan as its capital.

On September 18, 1960, through Republic Act 2786 dated June 19, 1960, the province of Surigao was divided into the present-day provinces of Surigao del Norte and Surigao del Sur.

• Surigao del Norte Province
• Surigao del Sur Province
• Dinagat Islands Province