In Bahia, in the beginning...
...there lived the indigenous people now commonly referred to as "Indians", and we can follow human recordings as far back as a people called the Gé. The Gé were pushed out by a people called the Tupinambá, and these were the people who were here when the first Europeans arrived (the coastal village of Olivença, Bahia remains home to a number of Tupinambá to this day).
Those first Europeans were Spaniards under the command of Vicente Yáñez Pinzón, who on January 26, 1500, landed to the north of what is now Bahia, close to the location of present-day Recife (capital of the state of Pernambuco). Pinzón had also been the captain of the Niña (as in the Nina, the Pinta, and the Santa Maria) when Christopher Columbus made his maiden voyage to the New World.
Next to arrive was the fleet of Pedro Álvares Cabral, who was actually on his way to India via a wide southernly swing out into the Atlantic Ocean (to avoid unfavorable currents) before heading east around Africa's Cape of Good Hope. Cabral's fleet landed in the territory which would come to be called "Brazil" (in English anyway; in Portuguese it's "Brasil") on the 21st of April, 1500, anchoring at a site he named "Porto Seguro" (or "Safe Port"; Porto Seguro is now a town located in present-day Bahia).
Cabral hadn't planned on landing there, at least not openly so. Common wisdom is that he was blown off course, but some people believe that he'd been secretly instructed by King Dom Manuel I to land for purpose of securing Portugal's rights to the territory. Whatever the case he did claim for Portugal the ground upon which he stood (this was on the 22nd of April, the day he himself went ashore), calling it the Ilha da Vera Cruz (Island of the True Cross). When it was discovered he'd actually been standing on a continent -- not an island -- the name was changed to Terra da Vera Cruz (Land of the True Cross).
Then on November 1st in 1501, a ship navigated by Amerigo Vespucci put into an enormous bay (November 1st is All Saints Day, and for this reason Amerigo named the bay "Bahia de Todos os Santos" -- "Bay of All Saints"). Amerigo also gave his own name to the entire continent via the use of a latinized form of it by mapmaker Martin Walseemüller in 1507. "America" at first applied only to the continent of South America.
Moving backwards in time somewhat, in 1493 Spain and Portugal had agreed that all of the Earth's territory west of Africa would be divided between themselves at a north-south line 100 leagues west of the Cape Verde islands (a league is 3 nautical miles, and a nautical mile is about 15% longer than a statute mile). In 1494 the line was moved 270 leagues further west.
The French weren't a party to this deal (called the Treaty of Tordesillas) and not wanting to be left out they began to exploit the South American coast. In order to counter the French incursions the Portuguese Crown divided Brazil up into 14 capitanias (this was between 1534 and 1536), all with straight, horizontal, north and south borders. The grantees of these capitanias were to be responsible for the administration and defense of their lands. Most of them failed miserably at it.
The Capitanias of Brazil
One of those who failed was the captain of Bahia, Francisco Pereira Coutinho, who arrived in 1536 and founded a village -- Vila Bahia -- on the site where the fort São Diogo and the church of Santo Antônio da Barra now stand. Both the fort and the church are readily visible from the beach at Porto da Barra. More about Captain Coutinho after another digression...
Sometime between 1509 and 1511 a ship sank off the coast of Bahia, and one of the few survivors was a man named Diogo Álvares Correa. Diogo was well-treated by the Tupinambás (after supposedly coming very close to being eaten by them) and from them he received the Indian name "Caramuru" (caramuru was the Tupinambás' name for a type of fish, and it is supposed that the new name had something to do with its soon-to-be owner having been found in the water).
Caramuru came to be so highly regarded that he was given Paraguassu -- daughter of the Tupinambá chief Taparicá -- as a bride. Salvador's first church -- Nossa Senhora da Graça -- was built by Caramuru and it is there that Paraguassu's body was eventually laid to rest. The church still stands (much grander than it was originally) and it was from the church that the neighborhood which grew up around it took its name: Graça ("Grace"). Catharina Paraguassu's mortal remains (she received the European name upon being baptized in France) are there to this day.
[The church is located in the Largo da Graça and is open Monday to Friday from 8 to 11:30 a.m. and from 2:30 to 5 p.m. Masses are Monday to Saturday at 7 a.m., and Sunday at 8 a.m. and 7 p.m. The church's phone number is 3247-4670.]
Catharina as depicted on the ceiling of her own church.
In the year 1537, a year after his arrival, Captain Coutinho -- the man whose word was law -- was on a boat which went down on the reefs off the southern end of the island of Itaparica. He was fished out of the water by Tupinambás but they weren't impressed by the position he held (they had a problem with it rather), and his fate was not to be that of the venerable Caramuru. After saving Captain Coutinho, they ate him.
The general failure of the captaincy system spurred the Portuguese Crown (in the person of Dom João III) into setting up a governorship of Brazil to be led by Thomé de Souza (often spelled "Tomé" nowadays). De Souza arrived in Bahia on the 29th of March, in 1549, and he went to work building a capital for Brazil and a place for himself to live (or for the governor-general to live and administrate from, rather). The latest incarnation of his palace, now called Palácio Rio Branco, sits on a commanding position overlooking the bay, on the same public square giving onto the Elevador Lacerda which takes one down to the lower city. The palace, in all its neo-classical glory, is open to the public.
Palácio Rio Branco, on the Praça Municipal. All it's missing is a cherry on top.
One strange twist in this complicated tale is the origin of a common Brazilian-Portuguese word. De Souza was accompanied by a group of Jesuits intent on spreading Christianity to the heathen natives of the "new" lands. The leader of the Jesuits was a padre by the name of Manoel da Nóbrega, and at a later point in history Salvador honored Nóbrega by bestowing his name upon a city street. Along this street grew up a string of places of ill-repute -- brothels and low-class bars -- and with time a shortened form of the street's name became synomynous with such places (and with a style of music commonly heard inside them): brega. (The name of the street -- Rua Padre Nóbrega -- has since been changed to Ladeira da Misericórdia).
What was the worry about converting the Indians? Their souls? Not exactly. Portugal's claim to Brazil was supported by the Catholic Church, the Treaty of Tordesillas having been recognized by Pope Alexander VI under the condition that the parties to the Treaty would convert the Indians to Christianity. The Church also allowed that those Indians who did not convert could be enslaved.
Well, up until now the principal source of wealth provided by Brazil had been pau brasil, or brazilwood (a source of a reddish dye). This was about to be supplanted by white gold -- sugar -- grown and harvested on immense plantations in Brazil's Northeast. Bahia's fortune was in the making, but it was to be a product of the sweat and blood of people who spent their lives producing and not partaking -- enslaved Africans and their descendents.
An estimated 1.5 to 2 million slaves were imported into Bahia before slavery was abolished in Brazil in 1888, four to five times the number imported into the entire United States of America (and some one-third to almost one-half of all slaves imported into Brazil).
http://www.slavevoyages.org/downloads/estimates-method.pdf (page 19)
Why enslave Africans and not Indians? To keep a longer story short, the successful conversion of Indians diminished the "pool" of available slaves. One result of this was such an outcry that Mem de Sá (the third governor of Brazil) approved a "just" war against the Caeté Indians for their treatment of Brazil's first bishop (they'd eaten him) allowing the Caeté (who lived in the interior of Bahia) to be taken as slaves. But things got out of hand and converted Indians were taken as well. Epidemics of smallpox, influenza, and measles followed, and then famine. These factors, combined with resistance and flight, led the Portuguese to (largely) abandon the enslavement of natives and to adopt the importation of Africans in chains. These people were to have an immeasurable impact on what Bahia was, and is.