Az Oxalaia quilombensis maradványai Brazília észak-keleti részén, késő krétakori üledékes kőzetből kerültek elő. Az eddig feltárt két koponyatöredék alapján az őshüllőt a szpinoszauruszok, azaz a tüskegyíkok közé sorolták, amelyek nevüket a hosszú csigolyanyúlványaikról kapták.
A leleteket leíró két brazil paleontológus - Alexander Kellner és Sergio Azevedo az ormánytöredék alapján rekonstruálta a koponyát. Az Oxalaia quilombensis majdnem másfél méter hosszú kobakja hosszú és keskeny volt, olyasféle, mint amilyennel a ma élő krokodilok büszkélkedhetnek. Más ragadozó őshüllőknek széles és masszív a fejük.
Az Oxalaia quilombensis óriásnak számított a szpinoszauruszok között is - testhossza 12-14 méter körüli lehetett, súlya pedig öt és hét tonna között mozgott.