Primeira expedição exploratória

Em 1501, uma grande expedição exploratória, a primeira frota de reconhecimento, com três naus, encontrou como recurso explorável apenas o pau-brasil, de madeira avermelhada e valiosa usada na tinturaria européia, mas fez um levantamento da costa. Comandada por Gaspar de Lemos, a viagem teve início em 10 de maio de 1501 e findaria com o retorno a Lisboa em 7 de setembro de 1502, depois de percorrer a costa e dar nome aos principais acidentes geográficos. Sobre o comandante, podem ter sido D. Nuno Manuel, André Gonçalves, Fernão de Noronha, Gonçalo Coelho ou Gaspar de Lemos, sendo este último o nome mais aceito. Em 1501, no dia 1 de novembro, foi descoberta a Baía de Todos os Santos, na atual Bahia, local que mais tarde seria escolhido por D. João III para abrigar a sede da administração colonial.

Alguns historiadores negam a hipótese de Gonçalo Coelho, que só teria partido de Lisboa em 1502. O Barão do Rio Branco, em suas Efemérides, fixa-se em André Gonçalves, que é a versão mais comumente aceita. Mas André Gonçalves fazia parte da armada de Cabral, que retornou a Lisboa quando a expedição de 1501 já partira para o Brasil e com ela cruzou na altura do arquipélago de Cabo Verde.

Detalhe do mapa "Terra Brasilis" (Atlas Miller, 1519), actualmente na Biblioteca Nacional de França.

Assim, diversos historiadores optam por Gaspar de Lemos, que entre junho e julho de 1500 havia chegado a Portugal com a notícia do descobrimento. O florentino Américo Vespúcio vinha como piloto na frota (e por seu nome seria batizado todo o continente, mais tarde). Depois de 67 dias de viagem, em 16 de agosto, a frota alcançou o que hoje é o Cabo de São Roque (Paraíba) e, segundo Câmara Cascudo, ali plantou o marco de posse mais antigo do Brasil. Houve, na ocasião, contatos entre portugueses e os índios potiguaras.

Ao longo das expedições, os portugueses costumavam batizar os acidentes geográficos segundo o calendário com os nomes dos santos dos dias, ignorando os nomes locais dados pelos nativos. Em 1 de novembro (Dia de Todos os Santos), chegaram à Baía de Todos os Santos, em 21 de dezembro (dia de São Tomé) ao Cabo de São Tomé, em 1 de janeiro de 1502 à Baía da Guanabara (por isso batizada de "Rio de Janeiro") e no dia 6 de janeiro (Dia de Reis) à angra (baía) batizada como Angra dos Reis. Outros lugares descobertos foram a foz do rio São Francisco e o Cabo Frio, entre vários. As três naus que chegaram à Guanabara eram comandadas por Gonçalo Coelho, e nela vinha Vespúcio. Tomando a estreita entrada da barra pela foz de um rio, chamaram-na Rio de Janeiro, nome que se estendeu à cidade de São Sebastião que ali se ergueria mais tarde.