In 1500, Portuguese explorer Pedro Alvares Cabral had set sail from Portugal in search of a western trade route to India. On April 22, his fleet of 13 ships arrived on the southern coast of Bahia (where Porto Seguro lies). Clambering ashore, the Portuguese planted a cross and held a mass at the spot they baptized Terra da Vera Cruz (Land of the True Cross). They spent the next 10 days exchanging trinkets with the local Tupi and evaluating the prospects of this palmy new land, which the Indians referred to as Pindorama (Land of Palms).

The only potential spoil that sparked their interest was a native tree with a rich, glossy hard wood that yielded a deep red dye. When the expedition returned to Portugal, word got out about this exotic timber, known as pau brasil—pau means wood and brasil is said to be a derivation of brasa, a red, hot coal. Although the Portuguese were still much more interested in the spices and ivory of their African and Asian colonies, over the next few decades, ambitious traders sailed across the Atlantic to the land of the brasil wood, which soon became shortened to “Brazil.” In return for metal tools and hardware, they had the Tupi cut down and harvest great quantities of brazilwood, whose crimson dye was highly coveted by European weaving factories.

Portugal only officially became interested in Brazil when French and Spanish merchants began showing a little too much interest in the new territory. Consequently, in 1532, in an attempt to stake claim to Brazil without actually have to take it on as a colony, King João III divided the Brazilian coast into 15 vast parcels, known as capitânias, which he distributed to various aristocratic cronies with the agreement that they would defend the territories, and hopefully find some more riches with which to further fill the crown’s coffers.

With the exception of Pernambuco, Bahia, and São Vicente (São Paulo), the capitânia concept proved a great failure. Without the presence of trained soldiers, Indians burned down fragile settlements and massacred their inhabitants. King João decided he would have to go the colonial route after all.

In 1549, he abolished the capitânias and named Tomé de Sousa as the new governor general of Brazil. Accompanied by a force of soldiers, Jesuit priests, ex-convicts, and bureaucrats, Sousa arrived in Salvador da Bahia that same year and claimed the city as the capital of the Brazilian colony.