Nazwa rodzajowa Oxalaia pochodzi od imienia afrykańskiego bóstwa Oxalá, którego kult pojawił się w Brazylii wraz z afrykańskimi niewolnikami. Epitet gatunkowy quilombensis odnosi się do osad quilombo, takich jak te na wyspie Cajual, zakładanych przez zbiegłych niewolników.
Budowa thumb|left|Wstępne porównanie wielkości Oxalaia i człowieka w postawach pływających
Holotypowe kości przedszczękowe mierzą razem 201 mm długości. Zachowany fragment ma 115 mm szerokości, jednak jego przyżyciową maksymalną szerokość szacuje się na 126 mm. Wysokość wynosi 103 mm. Na podstawie analizy czaszek spokrewnionych spinozaurydów długość czaszki Oxalaia szacuje się na 1,35 m, ustępowała więc spinozaurzej, mającej jakieś 1,75 m, wedle oszacowania w pracy włoskiego paleontologa Cristiano Dal Sasso i współpracowników w 2005. Kellner z zespołem porównał okaz Dal Sasso (MSNM V4047) z posiadanym fragmentem pyska Oxalaia w 2011. W ten sposób oszacowali na 12–14 m długość zwierzęcia i na 5-7 ton masę ciała. Czyniłoby to Oxalaia największym teropodem Brazylii. Na drugim miejscu jest Pycnonemosaurus, szacowany na 8,9 m.