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 (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 Manoel, 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.

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 potiguares.

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.

Em 1503 houve nova expedição, desta vez comandada (sem controvérsias) por Gonçalo Coelho, sem ser estabelecido qualquer assentamento ou feitoria. Foi organizada em função um contrato do rei com um grupo de comerciantes de Lisboa para extrair o pau-brasil. Trazia novamente Vespúcio e seis navios. Partiu em maio de Lisboa, esteve em agosto na ilha de Fernando de Noronha e ali afundou a nau capitânia, dispersando-se a armada. Vespúcio pode ter ido para a Bahia, passado seis meses em Cabo Frio, onde fez entrada de 40 léguas terra adentro. Ali teria deixado 24 homens com mantimentos para seis meses. Coelho, ao que parece, esteve recolhido na região onde se fundaria depois a cidade do Rio de Janeiro, possivelmente durante dois ou três anos.

Nessa ocasião, Vespúcio, a serviço de Portugal, retornou ao maior porto natural da costa brasileira, a Baía de Todos os Santos. Durante as três primeiras décadas, o litoral baiano, com suas inúmeras enseadas, serviu fundamentalmente como apoio à rota da Índia, cujo comércio de produtos de luxo – seda, tapetes, porcelana e especiarias – era mais vantajoso que os produtos oferecidos pela nova colônia. Nos pequenos e grandes portos naturais baianos, em especial no de Todos os Santos, as frotas se abasteciam de água e de lenha e aproveitavam para fazer pequenos reparos.

No Rio de Janeiro, alguns navios aportaram no local que os índios chamavam de Uruçu-Mirim, a atual praia do Flamengo. Junto à foz do rio Carioca (outrora abundante fonte de água doce) foram erguidas uma casa de pedra e um arraial, deixando-se no local degredados e galinhas. A construção inspirou o nome que os índios deram ao local (cari-oca, "casa dos brancos"), que passaria a ser o gentílico da cidade do Rio. O arraial, no entanto, foi logo destruído. Outras esquadras passariam pela Guanabara: a de Cristóvão Jacques, em 1516; a de Fernão de Magalhães (que chamou o local de Baía de Santa Luzia), em 1519, na primeira circunavegação do mundo; outra vez a de Jacques, em 1526, e a de Martim Afonso de Sousa, em 1531.

Outras expedições ao litoral brasileiro podem ter ocorrido, já que desde 1504 são assinaladas atividades de corsários. Holanda, em Raízes do Brasil, cita o capitão francês Paulmier de Gonneville, de Honfleur, que permaneceu seis meses no litoral de Santa Catarina. A atividade de navegadores não-portugueses se inspirava doutrina da liberdade dos mares, expressada por Hugo Grotius em Mare liberum, base da reação européia contra Espanha e Portugal, gerando pirataria alargada pelos mares do planeta.