The Sulu Archipelago was once part of Majapahit Empire and mentioned in the Old Javanese eulogy of Nagarakretagama by the name "Solot".

In June 1578 Francisco de Sande, Governor-General of the Spanish East Indies, dispatched captain Esteban Rodríguez de Figueroa and the Jesuit priest Juan del Campo and the coadjutor Gaspar Gómez to Jolo, resulting in a negotiated compromise where the Sulu sultan paid a regular tribute in pearls.

On 4 January 1638, Governor Sebastián Hurtado de Corcuera led a naval and military expedition of about 80 ships and 2,000 troops to attack Jolo, but Sultan Wasit put up stiff resistance.

However, Sultan Wasit's kuta army suffered a serious epidemic of tropical disease and he and his chieftains sought refuge in the Dungun area of Tawi-Tawi.

From 1663 to 1718, an interregnum of peace occurred because the Spanish troops were ordered to abandon the Zamboanga Peninsula, and forts south of that—and regroup in Manila to prepare for the impending attack of Koxinga—which never happened.

Hostilities resumed in the 18th century, triggered by the 1718 decision by governor Gen Juan Antonio dela Torre Bustamante to reconstruct the fort Real Fuerza de San José in Bagumbayan, Zamboanga.

In 1731, General Ignacio Iriberri lead a force of 1000 to Jolo and captured it after a lengthy siege, but the Spaniards again left after a few days.

In 1755, a force of 1,900 Spanish soldiers led by the captains Simeón Valdez and Pedro Gastambide was sent to Jolo in revenge for the raids by Sultan Muiz ud-Din, but the Spaniards were defeated.

In the second half of the 18th century, Great Britain became a new player in the archipelago After occupying Manila from 1762 to 1764, during the Seven Years' War between Spain, Great Britain and other European powers, the British Army withdrew to the south and established trading alliances between the Sulu Sultanate and the British East India Company.

In 1784, Aguilar conducted a series of unsuccessful assaults against Jolo and in 1796, Spanish admiral José Alava was sent from Madrid with a powerful naval fleet to stop the slave-raiding attacks from the Sulu Sea.

In 1803, Lord Richard Wellesley, the Governor-General of India, ordered Robert J. Farquhar to transfer trading and military operations to Balambangan island near Borneo; the resulting outpost lasted only until 1806.

In 1824, the Marina Sutil, a light and manoeuvrable naval force under Capitan Alonso Morgado was sent to confront the slave raiders in the Sulu Sea.

In 1850, Governor General Juan Urbiztondo continued with Claveria's campaign and annihilated the remaining Balangingi strongholds at Tungkil.

Spurred by their need to curb slave raiding, and concerned about other European colonial efforts in the region, the Spanish made a final bid to consolidate their rule in their southern frontier.

The British had established trading centres in Jolo by the 19th century and the French were offering to purchase Basilan Island from the Spanish government.

Captain Pascual Cervera was appointed to set up a garrison and serve as military governor; he served from March 1876 to December 1876 followed by Jose Paulin (December 1876 – April 1877), Carlos Martinez (Sept 1877 – Feb 1880), Rafael de Rivera (1880–81), Isidro G. Soto (1881–82), Eduardo Bremon, (1882), Julian Parrado (1882–84), Francisco Castilla (1884–86), Juan Arolas (1886–93), Caesar Mattos (1893), Venancio Hernandez (1893–96), and Luis Huerta (1896–99).

The Spaniards were never secured in Jolo, and by 1878 they had fortified the town with a perimeter wall and tower gates, built inner forts called Puerta Blockaus, Puerta España, and Puerta Alfonso XII, and two outer fortifications named Princesa de Asturias and Torre de la Reina when Sultanate of Sulu formally recognised Spanish sovereignty on Sulu and Tawi-tawi in middle of 19th century, but these areas remained partially ruled by the Spanish as their sovereignty was limited to military stations and garrisons and pockets of civilian settlements.

In 1880 Colonel Rafael Gonzales de Rivera, who was appointed by the Governor General, dispatched the 6th Regiment to Siasi and Bongao Islands.

The word “Ajuramentado” was coined by the Spanish colonel Juan Arolas after witnessing several such raids while serving with the Jolo garrison.

Early 20th century photographs of Jolo show a well-ordered town, neatly laid out in a grid of streets and blocks—characteristics of Spanish urbanism applied with a military rigidity.

As of 2013[update], short stretches of degraded perimeter wall still exist, but are covered by buildings or are partially demolished to less than 1 metre (3.3 ft) in height.