Dzisiejsza stolica stanu Bahia – Salvador – był określany przez Indian mianem Kirymuré lub Paraguaçu.
Europejczycy, którzy jako pierwsi dopłynęli do wybrzeży Bahia, napotkali tu plemię tupiniquim z rodziny tupinambá, które zamieszkiwało wówczas prawie cały pas wybrzeża stanu.
Okres kolonialny mały|Odkrycie Brazylii przez Cabrala w 1500 Pedro Álvares Cabral, który oficjalnie odkrył Brazylię 22 kwietnia 1500 roku, przybił właśnie do wybrzeży stanu Bahia, dokładnie w miejscu nazwanym Monte Pascoal (Góra Wielkanocna) w pobliżu dzisiejszego miasta Porto Seguro. W latach 1534–36 Portugalczycy podzielili Brazylię na 15 równoleżnikowych pasów, zwanych kapitaniami, na obszar stanu Bahia przypadały trzy kapitanie: Bahia de Todos os Santos, Ilhéus i Porto Seguro. W latach 1556–65 utworzono dwie kolejne kapitanie: Paraguaçu lub Recôncavo da Bahia oraz Wysp Itaparica i Tamarandiva.
Kapitanie były przyznawane kapitanom-donatariuszom (zwanym również gubernatorami), którzy mieli pełnię władzy administracyjnej i sądowniczej, mianowali urzędników i mogli przekazywać kapitanie spadkobiercom. Wszyscy donatariusze należeli do portugalskiej arystokracji, ale nie do najznakomitszych rodów.