Partindo de Lisboa, outra expedição exploradora, comandada por Gonçalo Coelho (?-1554), foi organizada em 1503, combinando ações da Coroa com as de negociantes. O governo de D. Manuel I (1469-1521) havia firmado, em 1502, contrato com comerciantes, tendo à frente o cristão-novo Fernão de Noronha (1470-1540). O acordo, prorrogado adiante, estabelecia que a terra fosse arrendada por um período de três anos para exploração da árvore chamada de pau-brasil. Em troca, os comerciantes comprometiam-se a construir feitorias, pagando à Coroa parte do lucro obtido. As feitorias instaladas serviriam como depósitos até que as caravelas portuguesas chegassem às terras ultramarinas.
Contudo, extrair essa espécie não era tarefa simples – as árvores nasciam dispersas nas grandes áreas de Mata Atlântica. Os europeus, então, necessitando do auxílio de quem conhecia a região, passaram a recorrer aos nativos, que cortavam a madeira. Ofereciam pelo trabalho objetos que os nativos desconheciam, como facas, pentes e espelhos. O tipo de relação, chamado de escambo, baseava-se na troca de produtos.
Naquela época, as pessoas que exploravam o pau-brasil – nas Terras de Santa Cruz (ibirapitanga, para os nativos) – eram chamadas de brasileiros. Contudo, os portugueses, possivelmente, não se interessaram em saber o porquê dos ameríndios chamarem de ibirapitanga a terra em que moravam. Talvez a nenhum deles ocorresse respeitar e manter os nomes já existentes dos lugares e das coisas. No entender do historiador Sérgio Buarque de Holanda, tal atitude significava um anseio de submeter o nativo. Era uma forma particular de os europeus encararem os mundos que descobriam. Assim, desde o princípio, a intenção dominadora marcava as imagens do novo território: dar nomes é conquistar; nomear é tomar; batizar é dominar. Para depois conceder.
Pesquisadores acreditam que, quando a expedição de Gonçalo Coelho alcançou as águas da Guanabara, tenha transposto a barra e, ali, permanecido por algum tempo. Há indícios da construção de uma fortificação, logo destruída pelos índios. Registros feitos nos diários de bordo dessa expedição narram um fato interessante, citado pelo professor Nireu Cavalcanti: o piloto João Lopes de Carvalho teria tido um filho com uma nativa. Se o fato for verídico, mesmo a criança tendo sido levada depois para o Reino, naquele momento teria nascido o primeiro carioca.
Quando as embarcações que compunham as expedições exploradoras retornavam, incontáveis novidades se espalhavam e novas viagens eram planejadas. E a caravela ostentando a cruz da Ordem de Cristo prosseguiria cruzando o Atlântico e despertando o interesse de intrusos.
