The youngest son of Jorge de Albuquerque Coelho, Matias was baptized as Paulo de Albuquerque, but he changed his name to Matias to honor his relative and godfather, Matias de Albuquerque, Viceroy of India.
The colony of Pernambuco in Brazil had been granted, in trust, to Matias's brother, Duarte de Albuquerque Coelho, under the system of hereditary captaincies (capitanias) established by the Portuguese crown as a device for administering their overseas possessions. Olinda, a town in Pernambuco colony, was Matias’s birthplace, but, as a young man, he left Olinda for Rio de Janeiro, where he trained for a military career.
He served three years in North Africa, and, in 1620, his brother, Duarte, asked him to serve as his agent in governing Pernambuco. There, he restored the personal authority of his family after almost fifty years of involvement in colonial administration only as absentees. He assumed the position of lieutenant-governor on 20 May 1620, and he went straight to work preparing the defenses of Pernambuco. (He remained in the post until November 1627.)
The following year, the huge size of Brazil led to the Portuguese colonies being divided into two estados (states); King Philip II created the State of Brazil, the most important colony, with Salvador (Bahia) as its capital, and, to its north, the State of Maranhão, with its capital at São Luís. Pernambuco was a captaincy within the State of Brazil.
When the first invasions of the colony of Brazil occurred in 1624 and 1625, the Dutch immediately seized Salvador (also known as Bahia), the capital of the State of Brazil, and, in the process, they captured the governor-general, Diogo de Mendonça Furtado. When news reached the colonial authorities elsewhere in the capitanias of Brazil that Mendonça had been deported to the Netherlands and imprisoned, they met at Vitória in the capitania of Espírito Santo and appointed Albuquerque to temporarily fill the post of governor-general of Brazil.
Once Bahia had fallen, Portuguese resistance was first reorganized under the self-appointed leader of the provisional government, Bishop Marcos Teixeira, who recruited about two thousand men, and, later, under the captain of nearby Recôncavo, Francisco Rolim de Moura. Thanks to their initiative, the Dutch were subjected to continual harassment, and they were contained, for the most part, within the boundaries of the capital, Bahia.
When he first received word of his appointment, Albuquerque's first instinct was to marshal his forces and march to the relief of occupied Bahia, but he was cautioned to bide his time. From his base at Olinda, at the end of 1624, he sent troops to reinforce the Portuguese guerillas based at Arraial do Rio Vermelho and at Recôncavo. The following year, an experienced hand, Diogo Luis de Oliveira, was found to assume the role of permanent governor-general.
Bahia did not stay long in the possession of the Dutch Republic. (This was during the period, 1580 to 1640, when Spain and Portugal were both ruled by a single Habsburg king.) The Spaniards were aware of the capture of Bahia a whole month earlier than the Dutch. A relief force was assembled and sent as quickly as possible. The West India Company was well aware of the Spanish relief force, but, due to bad weather, a Dutch fleet could not be sent to aid Bahia. It was also believed that the Dutch would be able to hold out until help could be sent. They were wrong. The armada, a Spanish-Portuguese fleet of 52 ships under the command of Don Fadrique de Toledo, arrived on 30 March 1625 in the bay of Salvador (Bahia de Salvador). After a siege lasting a whole month, the Dutch were forced to surrender the city on 30 April 1625. The Spanish-Portuguese allowed the Dutch occupation force and their ships to leave Bahia.
Albuquerque was called to Madrid for consultations with the king's ministers. There, rumors of a major new Dutch invasion of Brazil were in the air. As a partial response, Albuquerque was appointed superintendent of fortifications and inspector-general of the northern captaincies in the State of Brazil. However, Spain was embroiled in the Thirty Years' War, and, while the Dutch threat to Brazil was considered credible, resources were more likely to be devoted to military operations on the European continent and to shore up the defenses of the gold- and silver-producing colonies that fed the Caribbean treasure fleets. Albuquerque returned to South America in 1629 with the meager resources the King's treasury could spare for the defense of Brazil, – a bit of money, in silver coin, and twenty-seven Portuguese soldiers.
In February 1630, the long-anticipated Dutch invasion finally arrived, and it immediately overwhelmed Olinda and its port, Recife. Albuquerque and his smaller force was compelled to retreat, but, before doing so, they managed to burn the sugar warehouses at the port of Recife, preventing the Dutch West India Company from using them and denying them the profit of their contents. He re-organized the Portuguese-Spanish defense on high ground at a place called Arraial Velho do Bom Jesus, about halfway between Olinda and Recife, and, in doing so, he established a fortified position that was quite easily defended, and its well-chosen location, for the most part, confined the Dutch within the towns. Albuquerque maintained this cordon until 1635, even though his position at Arraial came under repeated Dutch attacks.
Some of these attacks on Arraial were masterminded by a man named Domingos Fernandes Calabar, a mulatto born in Porto Calvo, Alagoas, then within the colony of Pernambuco. Before the ten-year truce between Portugal and the Netherlands expired in 1621, Dutch traders had regularly called at ports in Portuguese Brazil and through these contacts, Calabar had, at Recife, managed to talk his way into a job working for the Dutch West Indies Company in the Netherlands.
When relations between Portugal and the Dutch soured in 1624 because of the seizure of Bahia, Calabar found himself in a delicate position, torn between a loyalty to the place of his birth and a loyalty to the payer of his wages. By 1630, he was back in Recife, where his knowledge of the local geography made him a valuable man to know. The Dutch had become familiar with the rivers and streams, the swamps and islets, along the coasts, but their knowledge of the interior was almost nil. As a merchant and smuggler, Calabar knew every turn in every inland road. In fact, he had a remarkable sense of the local topography.
In April 1632, Calabar went to the Dutch authorities and expressed his willingness to help. He soon demonstrated that he was especially adept at planning and executing ambushes. The name of Calabar came to the attention of Albuquerque and the other Portuguese, and, because of his frequent successes, he developed a considerable reputation among them for his cleverness and his treachery.
After a time, the Dutch decided to evacuate Olinda, burn it, and concentrated on Recife.