La bahía que le da el nombre fue descubierta el 1 de noviembre -dedicado, por el calendario católico a Todos los Santos-, por la primera expedición exploradora en 1501.
Cuando su donatario llegó, dos años más tarde, ya existía en la bahía de Todos los Santos una pequeña comunidad de europeos entre los cuales se destacaba Diogo Álvares Correia "el Caramuru" con su esposa Catarina Paraguaçú y muchos hijos.
Negociada la paz, al retornar a la Vila do Pereira, el donatario y los colonos naufragaron durante una tempestad frente a la Isla de Itaparica, siendo los sobrevivientes capturados y devorados por los indígenas (1547).
En 1556 fueron cedidas por el gobernador general las islas y tierras del Recôncavo que se transformarían, más tarde, en "capitanías autónomas": En 1553 asumió como gobernador general Duarte da Costa.
Al finalizar el gobierno de Mem de Sá en 1572 el territorio fue dividido en dos gobiernos generales, uno al norte en Bahía y el otro al sur en Río de Janeiro, para el primero fue nombrado gobernador general Luís Brito e Almeida y para el segundo António Salema, hasta que el gobierno fue reunificado en 1578 con Lourenço da Veiga como único gobernador general con sede en Bahía.
De esta manera Brasil pasó a tener dos unidades administrativas: Estado del Maranhão y Estado del Brasil, este último con capital en Salvador (de Pernambuco a la actual Santa Catarina).