Recibió el apodo de Caramuru (palabra tupí que significa morena[1]) por los indios tupinambás.
A lo largo de cuarenta años, Correia mantuvo contactos con los barcos europeos que atracaron en Bahía.
Las relaciones comerciales con los normandos le llevaron, entre 1526 y 1528, a visitar Francia, donde fue bautizada su mujer en Saint-Malo, pasando a llamarse Catarina Álvares Paraguaçu, en honor de Catherine des Granches,, la esposa de Jacques Cartier, que fue su madrina.
En la misma ocasión, fue bautizada también otra india tupinambá, Perrine, en lo que se basa la leyenda de que varias indias, por celos, habríanse ahogado en el mar para acompañar a Caramuru cuando éste partió para Francia con Paraguaçu.
Su vida inspiró al fraile brasileño Santa Rita Durão a escribir el poema épico Caramuru en 1781.