Lorsque le jour de Pâques arrivera, au pied de l'immense croix dressée au bas de la colline baptisée pour la circonstance « monte Pascoal », des prêtres portant chasubles célébreront avec ferveur un office religieux devant les 1 100 marins et soldats de la flotte portugaise et une multitude d'hôtes amérindiens, emplumés et armés d'arcs et de flèches, fort curieux et amusés par cette cérémonie appelée « grand-messe ».

Le récit de cette insolite relation entre ces deux peuples, qui avaient vécu jusque-là dans la plus complète ignorance l'un de l'autre, est parvenu en Europe grâce à une lettre datée du 1^er mai et adressée au roi de Portugal par le greffier de l'amiral Cabral, Pedro Vaz de Caminha. Couvrant de son écriture vingt-sept pages, le scribe de l'expédition a livré à chaud ses premières impressions. La terre nouvellement abordée est « si gracieuse que, si on veut en tirer profit, assure-t-il, tout y poussera, si nombreux sont les cours d'eau qu'elle possède ». Quant aux hommes qui la peuplent, « ils paraissent d'une telle innocence que si nous comprenions leur langue et eux la nôtre, on en ferait bien vite des chrétiens ».

À l'issue de la cérémonie de prise de possession, les vaisseaux retourneront vers le large pour traverser l'Atlantique sud, franchir le cap de Bonne-Espérance et poursuivre leur route vers les Indes touchées deux ans plus tôt par les caravelles de Vasco de Gama. Aucun des membres de cette expédition ne reverra l'île de la Vraie Croix.

La flotte placée sous le commandement de Cabral avait appareillé du port de Lisbonne le 9 mars 1500. Elle avait été soigneusement préparée par le roi de Portugal dès le retour de Vasco de Gama. Dans l'esprit de celui-ci, elle devait inaugurer un nouveau type d'expéditions. À présent que la voie maritime menant aux Indes était connue, une nouvelle ère commençait : celle des expéditions militaires. La progression dans l'hémisphère Sud de ses navigateurs lui permettait de proclamer qu'il serait bientôt le maître de l'océan Indien et de décréter qu'aucun navire ne pourrait y faire du commerce sans son autorisation.

Pour parvenir à ses fins, Manuel I^er aura à faire face à la résistance des Arabes, maîtres du commerce dans cette partie du monde, puis à la coalition formée par les intérêts lésés des Vénitiens, des Arabes et du sultan d'Égypte. Aussi l'ordre de mission confié à Cabral avait été formel : rééditer la prouesse de Vasco de Gama et contraindre, si nécessaire par la force, le rajah de Calicut à obtempérer.

Nommé à la tête de cette flotte, Pedro Álvares Cabral, qui venait de fêter son trentième printemps, n'avait jamais navigué. Totalement inconnu des écumeurs de mers des deux rives du Tage, ce petit noble était en revanche fort bien introduit à la Cour. Il avait en effet épousé une riche dame de compagnie de la reine et appartenait au puissant ordre des Chevaliers du Christ, qui revendique depuis deux siècles l'héritage des Templiers. Avisé, le roi avait désigné deux prestigieux capitaines pour le seconder : Bartholomeu Dias, le premier Européen à avoir doublé le cap de Bonne-Espérance en janvier 1488, et Nicolau Coelho, une vraie légende des mers qui sera à ses côtés à bord du vaisseau amiral.

Afin d'éviter les tempêtes qui rendent dangereuse la navigation le long des côtes africaines et de contourner les grands calmes rencontrés de part et d'autre de l'équateur, Cabral, sur les conseils de Vasco de Gama, avait fait route plus à l'ouest et maintenu le cap vers le sud avant de voir poindre la côte inconnue du Brésil. C'est donc tout à fait fortuitement qu'il a fait escale en un point du Nouveau Continent et, de ce fait, découvert l'île de la Vraie Croix.

Rebaptisée par d'autres compatriotes « Terra de Santa Cruz », la Ilha de Vera Cruz ne gardera pas non plus ce nom. La terre nouvelle se nommera Brésil à cause d'une essence à noyau rouge très répandue sur son littoral et très prisée par les teinturiers pour le colorant qu'elle contient : le bois de braise, ou bois brésil. Attirés par cette essence et nullement liés par le traité de Tordesillas par lequel Espagnols et Portugais s'étaient partagés le monde en 1494, les marins de Dieppe et de Honfleur prendront l'habitude de se rendre sur la côte du bois brésil en francs-tireurs pour se procurer cette précieuse plante tinctoriale. D'autres navigateurs européens suivront leur exemple et visiteront à leur tour ces rivages impressionnants par leur épaisse couverture forestière et l'abondance de leurs cours d'eau. Ainsi les tribus Pataxos apprendront-elles de la bouche de leurs voisins Tupi qu'elles n'ont pas été les seules à recevoir ces étranges visiteurs descendus du ciel à l'aide d'immenses voiles.