O pau-brasil, primeiro produto de exploração e exportação do país, devido ao interesse comercial pela tinta vermelha extraída de sua madeira, acabou dando o nome definitivo à recém batizada Terra de Santa Cruz. Os europeus já conheciam outras árvores que produziam corantes similares e foi delas que veio a denominação do pau-brasil: do árabe wars, nome de uma planta do Iêmen usada em tingimentos, passou para verzino, termo utilizado na Itália medieval para designar uma outra árvore com corante, a madeira-sapão, e daí para o francês brésil, brasil em português. Os diversos europeus que vieram explorar e contrabandear a madeira se referiam a este local como Terra Brasilis, Terra Brazílica, Costa do Pau Brasil e assim ficou. A abundância, a falta de vigilância ou leis permitiram, durante décadas, a exploração barata do pau-brasil, o que colocou seu corante com muita vantagem sobre os outros do Oriente já conhecidos pelos europeus.
Os povos originários chamavam a árvore de arabutã, ibirapitanga, ibirapiranga, ibirapitá ou orabutã, nomes derivados dos termos tupis ybyrá ("pau") e pytanga ("vermelho"). Essas denominações, assim como a de Terra de Santa Cruz, foram praticamente esquecidas, apesar de os indígenas terem sido a principal mão-de-obra para cortar as madeiras e carregar para os navios, inicialmente em troca de ferramentas, armas e utensílios, e, em um segundo momento, obrigados à força.
Entre os primeiros europeus que estiveram no Brasil, o aventureiro alemão Hans Staden (c.1525-1576) narrou em diversas passagens de seu relato A verdadeira história dos selvagens, nus e ferozes devoradores de homens, encontrados no Novo Mundo, a América, que acabou conhecido como Duas Viagens ao Brasil, publicado na Alemanha em 1557, as disputas entre portugueses e franceses para explorar essa madeira. "Navegamos quarenta milhas até um porto de nome Paraíba, onde carregamos pau-brasil e onde queríamos nos abastecer de mais mantimentos junto aos selvagens. Ao chegarmos, encontramos um navio da França que estava carregando pau-brasil. Atacamo-lo e esperávamos tomá-lo; mas eles danificaram nosso grande mastro com um tiro e escaparam. Entre nossa tripulação houve alguns mortos e alguns feridos", escreve no capítulo ilustrado pela imagem acima (Duas viagens ao Brasil : primeiros registros sobre o Brasil, Editora L&PM, Porto Alegre: 2011).
Staden também fornece exemplos dos escambos feitos por franceses e indígenas para o contrabando de pau-brasil: "O chefe do barco no qual eu estava tinha uma escopeta e um pouco de pólvora. Ambos lhe tinham sido dados por um francês em troca de pau-brasil". Em outro momento do livro, "eles sabiam muito bem que os franceses eram tão inimigos dos portugueses quanto eles próprios, pois os franceses vinham todo ano de navio e traziam-lhes facas, machados, espelhos, pentes e tesouras. Em troca, davam-lhes pau-brasil, algodão e outras mercadorias, como penas e pimenta. Por isso eram bons amigos".
O frade franciscano francês André Thevet (1516-1592), que esteve no Brasil em 1555, também registrou o pau-brasil em sua obra Les singularitez de la France Antarctique, publicada no mesmo ano do livro de Hans Staden: "Esta árvore, que na língua dos selvagens recebe o nome de orabutan, é uma planta de rara beleza. A casca, cinzenta por fora, recobre um tronco que é tanto mais vermelho quanto mais próximo do cerne, sua parte mais excelente e procurada". Na gravura acima, ele registrou indígenas derrubando a árvore.
Durante todo o século XVI, a exploração do pau-brasil continuou quase até seu esgotamento, sendo aos poucos substituída por outras atividades econômicas, como as plantações de cana-de-açúcar, café ou a extração de ouro e outros minérios. "Enquanto na tinturaria o pau-brasil foi substituído, praticamente de um dia para o outro, pelas anilinas sintéticas, cresceu a demanda no setor de fabricação de arcos de violino. De modo que, em vez de diminuir, a exploração da árvore prosseguiu e prossegue até hoje, inexorável, a despeito da ameaça real e inconteste de sua extinção", escreveu a pesquisadora suíça Malou Von Muralt, em seu artigo "A árvore que se tornou país" (Revista da USP, São Paulo, n.71, setembro/novembro, 2006). Nativo da Mata Atlântica, o pau-brasil sofreu e ainda sofre com a extração e a ocupação humana. Reduzida a menos de 7% de sua área original, que era de mais de 1,3 milhão de km2 antes da chegada dos colonizadores, a região que se estende da costa do Rio Grande do Norte até o Rio de Janeiro é hoje ocupada por 61% da população brasileira.
Em 2016, a árvore-símbolo do Brasil ganhou uma nova denominação científica. Antes considerado pertencente ao gênero Caesalpinia, e denominado como Caesalpinia echinata, pelo naturalista francês Jean-Baptiste de Lamarck (1744-1829), em 1785, o pau-brasil foi rebatizado de Paubrasilia echinata por cientistas que descobriram, através da análise de sequências de DNA, tratar-se de uma espécie única e por isso pertencente a um gênero distinto.