Izolowana i fragmentaryczna lewa kość szczękowa (MN 6119-V) została przypisana do tego samego rodzaju, ponieważ charakteryzowały ją te same typowe cechy spinozaurydów. Kość tę odkryto na powierzchni skały, być może przemieściła się z jej oryginalnego położenia dzięki erozji. Oba fragmenty kości znaleziono na wyspie Cajual w Maranhão w Regionie Północno-Wschodnim Brazylii. Znajdują się w Muzeum Narodowym w Rio de Janeiro. W 2018 w muzeum wybuchł pożar, być może niszcząc okazy Oxalaia, jak też wiele innych skamieniałości przechowywanych w tej placówce. Prócz fragmentarycznych kości czaszki liczne zęby Spinosauridae odnotowywano już wcześniej z Laje do Coringa.
Odkrycia Oxalaia i późnokredowych Pepesuchus i Brasiliguana ogłoszono podczas prezentacji Brazylijskiej Akademii Nauk w marcu 2011. Machado opisała Oxalaia jako dominującego gada na terenach obecnej wyspy Cajual. Opis gatunku sporządzili brazylijscy paleontolodzy Alexander Kellner, Elaine Machado, Sergio Azevedo, Deise Henriques i Luciana Carvalho. Publikacja weszła w skład 20 prac dotyczących prehistorycznej bioróżnorodności opublikowanych przez Akademię w marcu 2011. Gatunek typowy Oxalaia quilombensis stanowi ósmy oficjalnie nazwany gatunek teropoda z Brazylii.