Oxalaia is known from the holotype MN 6117-V, fused premaxillae of a very large individual and from the referred fragment MN 6119-V, an isolated and incomplete left maxilla, which were found on Cajual Island, Maranhão of northeastern Brazil. Fossils of Oxalaia were recovered in 2004 from the Laje do Coringa locality of the Alcântara Formation, part of the Itapecuru Group of the São Luís Basin. Besides these bone fragments, numerous spinosaurid teeth had earlier been reported from the site.
The genus was named by Alexander Wilhelm Armin Kellner, Sergio A.K. Azevedeo, Elaine B. Machado, Luciana B. Carvalho and Deise D.R. Henriques in 2011 and the type species is Oxalaia quilombensis. The specific name quilombensis refers to the quilombo settlements, such as on Cajual Island, which were founded by escaped slaves. Estimates suggest that it was 12 to 14 metres (39 to 46 ft) in length and 5 to 7 tonnes (5.5 to 7.7 short tons) in weight —- it is the largest theropod known from Brazil and the eighth officially named species of theropod from Brazil.