Partida e chegada a uma nova terra
A frota, sob o comando de Cabral, partiu de Lisboa em 9 de março de 1500 ao meio-dia. No dia anterior, a tripulação tinha recebido uma despedida pública que incluíra uma missa e comemorações com a presença do rei, da corte e de uma enorme multidão. Na manhã de 14 de março, a frota passou por Grã Canária, a maior das Ilhas Canárias. Em seguida, partiu rumo a Cabo Verde, uma colônia portuguesa situada na costa oeste da África, que foi alcançada em 22 de março. No dia seguinte, uma nau com 150 homens, comandada por Vasco de Ataíde, desapareceu sem deixar vestígios. A frota cruzou a Linha do Equador em 9 de abril e navegou rumo a oeste afastando-se o mais possível do continente africano, utilizando uma técnica de navegação conhecida como a volta do mar. Os marujos avistaram algas-marinhas no dia 21 de abril, o que os levou a acreditar que estavam próximos da costa. Provou-se estarem certos na tarde do dia seguinte, quarta-feira, 22 de abril de 1500, quando a frota ancorou perto do que Cabral batizou de Monte Pascoal (uma vez que aquela era a semana da Páscoa). O monte localiza-se no que hoje é a costa nordestina do Brasil.
Carta de Pero Vaz de Caminha ao rei D. Manuel I, comunicando sobre o descobrimento da Ilha de Vera Cruz.
Os portugueses detectaram a presença de habitantes na costa, e os capitães de todos os navios reuniram-se a bordo do navio de Cabral no dia 23 de abril. Cabral mandou Nicolau Coelho, capitão que havia viajado com Vasco da Gama à Índia, para desembarcar e estabelecer contato. Ele pisou na terra e trocou presentes com os indígenas. Após Coelho voltar, Cabral ordenou que a frota rumasse ao norte, onde, após 65 km de viagem, ancorou em 24 de abril no local que o capitão-mor chamou de Porto Seguro. O lugar era um porto natural, e Afonso Lopes (piloto do navio principal) trouxe dois índios a bordo para conversarem com Cabral.
Assim como no primeiro contato, o encontro foi amistoso e Cabral ofereceu presentes aos nativos. Os habitantes eram caçadores-coletores da idade da pedra, a quem os europeus atribuiriam o rótulo genérico de ”índios”. Os homens coletavam alimento por meio da caça e da pesca, enquanto as mulheres se dedicavam à agricultura em pequena escala. Eles se dividiam em inúmeras tribos rivais. A tribo que Cabral encontrou foi a tupiniquim. Alguns deles eram nômades e outros sedentários — tendo conhecimento do fogo, mas não dos metais. Algumas poucas tribos praticavam o canibalismo. Em 26 de abril (domingo de Páscoa), conforme cada vez mais nativos curiosos apareciam, Cabral ordenou aos seus homens a construção de um altar em terra, onde uma missa católica foi celebrada por Henrique de Coimbra — a primeira a sê-lo no solo do que mais tarde viria a ser o Brasil.