A Spanish expedition led by Luis de Guzman set foot in Albay in 1569. The expedition came from southern route that first explored the islands of Masbate, Ticao and Burias, then the southern Bicol Peninsula (which the Spanish later named Ibalon).  De Guzman may have traveled inland reaching the town of Camalig, although some believe that this expedition was probably limited mostly to the area of Sorsogon.  De Guzman was accompanied by missionaries who Christianized the inhabitants of Ibalon, Camarines and Burin.

In July 1573, Juan de Salcedo (grandson of Governor-General Legazpi) led 120 soldiers and Agustinian missionaries in another expedition from the north, entering the Bicol River from San Miguel Bay to Lake Bato.   They found Villa Santiago de Libon (Libong or Libon),  and reached the town of Albaybay (interpreted by the Spaniards Angtabay) then proceeded to the neighboring island of Catanduanes.  The name of Angtabay was changed to Albaybay and shortened to Albay.  In 1616, the Pueblo of Albay served as the capital of Partido de Ibalon with its capital in Camalig (Daraga). Ibalon included the modern provinces of Albay, Sorsogon, and parts of Camarines Sur, Masbate, and the islands of Catanduanes, Ticao and Burias.

The partido de Ibalon under the original control of Camarines (from Caceres or Naga) fell under the jurisdiction of the military government at Iloilo. Under the earlier arrangement, Camarines had included the entire Bicol Region; but apparently travel from Caceres to Albay was so difficult at that time that it was easier to govern Albay from Iloilo via the sea.  Early towns during this period included Camalig, created in 1569; Libon, founded in 1573; Oas, created in 1587; Polangui, organized in 1589; and Malinao, created in 1600. Then the Partido de Ibalon was divided into two provinces known as Ibalon and Camarines (or Ambos Camarines), with the boundary located between Cagsawa (Daraga) and Camalig.  The present towns of Camalig, Guinobatan, Jovellar, Ligao, Oas, Polangui and Libon were then part of Ambos Camarines, and Lagonoy, Sangay, whereas Caramoan belonged to Ibalon province.  The province of Ibalon had 38 pueblos in 1834 and was formally renamed Albay in 1836.

In 1846, Governor-General Narciso Claveria decreed the separation of the islands of Masbate, Ticao, and Burias, which had formerly fallen under the administrative jurisdiction of Albay, to form the commandancia-politico-militar of Masbate.  At the same time, Albay, then a politico-military province, ceded the towns of Lagonoy, Caramoan and Sangay on the Caramoan peninsula to the province of Camarines Sur, in exchange for Camalig, Guinobatan, Mauraro, Ligao, Oas, Polangui, Libon, Donsol and Quipia (Jovellar).  Later, Donsol was placed in Sorsogon. Sorsogon province was separated from Albay on October 17, 1894.

With the fall of the Spanish regime during the Philippine Revolution in 1898, a short-lived provincial government was set up under the revolutionary regime.  This was soon displaced by an American military established in April 26, 1901 then civil government. At this time, Albay included the formerly independent island-province of Catanduanes as a municipality.  In 1905, Catanduanes was made a sub-province of Albay, and in 1945, it was separated and organized again into a separate province.  Albay was created as a province under Act 2711 on March 10, 1917, which comprised the following municipalities; Bacacay, Camalig, Daraga, Guinobatan, Jovellar, Legazpi, Libong (Sto. Domingo), Libon, Ligao, Malilipot, Malinao, Manito, Oas, Polangui, Rapu-Rapu, Tabaco and Tiwi.  Legazpi was the former town of Albay, which had been renamed Legazpi in 1836, changed to Albay again in 1908, and finally back to Legazpi when it became a chartered city in 1948.  In 1963 the additional municipality of Pioduran was created.