Uma das mais antigas e importantes companhias de navegação do Brasil, a Companhia Bahiana de Navegação foi fundada em 1836, por um certo João Diogo Sturtz, representante de capitalistas ingleses, para estabelecer um serviço regular de navegação.
Navio Del Rei em Jaguaripe
Em 1839 a empresa iniciou suas atividades, dirigida pelo inglês Armand Hadfield Wood, fazendo três viagens semanais para Cachoeira, duas para Santo Amaro e uma para Nazaré, passando pela ilha de Itaparica, com quatro vapores; o Bahia, o Catharina Paraguassú, o Todos os Santos e o São Salvador. Em 1842 a empresa incorporou um quinto vapor, o Caramuru, enquanto os vapores Todos os Santos e São Salvador foram retirados de linha.
Navio Paraguassú
Devido à má administração e à falta de subvenção do governo, a Bahiana prestava um serviço deficiente o que levou o governo a rescindir sua concessão e a requerer sua falência, em 1847, substituindo-a por outra empresa, a Bomfim, que logo recebeu uma subvenção do governo e adquiriu o acervo da Bahiana.
Navio Paranaguá
Inicialmente a Bomfim operou com três vapores, o Bahia, o Bonfim e o Catharina Paraguassú , fazendo as linhas apenas do recôncavo. Em 1852 a companhia adquiriu um quarto vapor, o D. Pedro II, iniciando o serviço de navegação costeira para Valença, e incluindo escalas nas cidades de São Francisco do Conde, Jaguaripe e Maragogipe, na rota para Cachoeira.
Navio Canavieiras
Em 1853 o governo da província deu uma concessão para o empresário Antonio Pedrozo de Albuquerque, que havia feito fortuna com o tráfico de escravos, para estabelecer uma nova empresa de navegação costeira, a Santa Cruz, que passou a operar com três navios; o Santa Cruz, o Paraná e o Cotinguiba.
A linha para o sul ia até Caravelas, fazendo escalas em Camamú, Ilhéus, Canavieiras e Porto Seguro, e a do o norte até Maceió, fazendo escala em Estância, São Cristóvão, Aracaju e Penedo.
Em 1855 a epidemia de cólera que atingiu as cidades do recôncavo e uma seca que durou quatro anos, causaram uma diminuição no movimento, deixando a Bonfim em má situação.
Em 1858, Antonio Pedrozo de Albuquerque se uniu a outros dois capitalistas baianos, Francisco Gonçalves Martins e Francisco Justiniano de Castro Rebello, e adquiriu a Companhia Bonfim, fundindo-a com a Santa Cruz e fazendo renascer a Companhia Bahiana de Navegação, que passou a atender também a navegação costeira, entre Maceió e Caravelas, com oito navios; Gonçalves Martins, Valéria Sinimbú, Santa Cruz, Paraná, Cotinguiba, Pedro II, Cachoeira, Progresso e Paraguassú.
Em 1862, capitalistas ingleses que estavam investindo nos serviços de iluminação à gás, telégrafo e bondes em Salvador, adquiriram o controle da companhia, que passou oficialmente a se chamar Bahia Steam Navigation Company, tendo como presidente John Watson.
A nova empresa aumentou para 20 o número de vapores, substituindo alguns de madeira por outros de ferro, incluindo a cidade de Barra do Rio de Contas (Itacaré), nas escalas para o sul e implementando as linhas na orla marítima de Salvador entre a Barra, Água de Meninos, Jequitaia, Roma, Bonfim, Itapagipe, São Tomé de Paripe, Boca do Rio e Restinga.
Também iniciou a navegação no rio São Francisco, entre Penedo e Piranhas, passando por Propriá, Colégio, São Braz, Traipú, Curral das Pedras, Ipanema, Lagoa Funda, Pão de Açúcar e Armazém, e em Alagoas, nas lagoas Norte (Mundaú), atendendo as localidades de Coqueiro Seco e Santa Luzia e na lagoa de Manguaba, atendendo Pilar e Cidade das Alagoas, além das localidades de São Miguel e Barra de São Miguel.
A Bahiana também construiu um pequeno trecho de ferrovia de pouco mais de 7 Km, entre as lagoas de Mundaú, Manguaba e o porto de Maceió.
Toda essa expansão resultou no endividamento da empresa, que veio a sofrer prejuízos com a guerra do Paraguai e com uma longa crise na Europa.
Como resultado a empresa começou a piorar a prestação de serviços, a conservação dos navios e sofreu alguns naufrágios, tendo sua frota reduzida para 14 navios, o que resultou na sua venda para o Visconde Pereira Marinho, rico comerciante, também ex-traficante de escravos e que já operava uma frota de barcos à vela transportando charque do Rio Grande do Sul.
Assim, em 1876 a Companhia Bahiana de Navegação voltou a ser uma empresa brasileira tendo transferinda sua sede de Londres para Salvador.
Isso não impediu que as dificuldades continuassem aumentando e que, em 1894, ela fosse novamente vendida, desta vez para uma nova empresa nacional de navegação costeira, o Lloyd Brazileiro.
Em 1905 ela foi adquirida pelo governo do Estado da Bahia condição em que permaneceu até 1957, quando passou a ser uma empresa de economia mista. Com o golpe militar, a empresa que já era deficitária, teve suas linhas restritas quase que exclusivamente ao recôncavo, tendo que entregar os navios Lúcio Meira, Silvio Motta e Guarujá, ao Lóide Brasileiro e encerrando suas linhas para o exterior, que lhe rendiam divisas em dólar.
Em 1967 é idealizado o sistema ferry-boat, que incluía a construção da Ponte do Funil, ligando a Ilha de Itaparica à Nazaré e a estrada que prosseguia até Valença, ligando Salvador ao sul do estado. Em dezembro de 1972 o primeiro ferry, o Agenor Gordilho começou a operar.
