Ostafrikasaurus byl předběžně odhadnut na 8,4 metru (28 stop) dlouhý a vážící 1,15 tuny (1,27 krátké tuny; 1,13 dlouhé tuny). Holotyp zubu je 46 milimetrů (1,8 palce) dlouhý, má zakřivenou přední hranu a je oválného tvaru v průřezu. Zub vykazuje zoubky, které – na spinosauří poměry – jsou nezvykle velké, více než u jakéhokoli jiného známého taxonu. Přední i zadní řezné hrany jsou zoubkované, se dvěma až čtyřmi zubníky na mm (0,04 palce). Zub má také podélné hřebeny na obou stranách a vnější smaltovaná vrstva má vrásčitou strukturu v oblastech mezi a bez hřebenů.
Mezi nejstaršími známými fosiliemi spinosauridů může být Ostafrikasaurus důležitý pro pochopení evolučního původu spinosauridů a jejich anatomických adaptací. Ze srovnání s jeho pozdějšími příbuznými Ostafrikasaurus naznačuje, že spinosauří zuby se staly kuželovitějšími a během svého vývoje ztratily své vroubkování. To je možná důsledek toho, že se staly více specializovanými pro žravou (rybožravou) stravu, jak bylo naznačeno pro čeleď na základě fosilních důkazů a polovodních adaptací, které vykazovalo mnoho druhů. Je také známo, že se živili pterosaury a dalšími dinosaury. Ostafrikasaurus žil v subtropickém až tropickém prostředí vedle mnoha dalších dinosaurů, stejně jako pterosaurů, krokodýlů, ryb, savců a bezobratlých. Vzhledem ke svému stáří a umístění Ostafrikasaurus naznačuje, že spinosauridi mohli být globálně rozšířeni před rozpadem Pangey.
V roce 2000 američtí paleontologové James Madsen a Samuel Welles odkázali zuby L.? stechowi na Ceratosaurus sp. (nejistého druhu), protože připomínaly zuby z premaxilárních a zubních čelistních kostí Ceratosaura, teropoda ze severoamerické Morrisonovy formace. V roce 2007 americký paleontolog Denver Fowler místo toho navrhl, že zuby patří spinosauridnímu dinosaurovi podobnému Baryonyxovi, což by ho zařadilo mezi nejstarší známé fosilie spinosaurida, a tedy jedny z nejstarších důkazů o této skupině. Tuto analýzu zpracoval francouzský paleontolog Eric Buffetaut, který v tomto roce zuby zkoumal, a v roce 2008 odkázal exemplář MB R 1084 na Spinosauridae. Bufetaut zjistil, že tento exemplář se liší od ostatních zubů dříve označovaných L.? stechowi a že jiný izolovaný zub (MB R 1091) z prostředního dinosauřího člena by mohl představovat stejné zvíře. Zpochybnil také Janenschovo předběžné přidělení zubů pochybnému rodu Labrosaurus, které bylo založeno na mizivých pozůstatcích z Morrisonova souvrství, které byly později připsány Allosaurovi. Buffetaut dále poznamenal, že zub L. sulcatus ilustrovaný Marshem je nyní považován za patřící Ceratosaurovi. Podobně byl L. stechowi odsunut jako pochybný ceratosaurián příbuzný Ceratosaurovi.
V roce 2011 německý paleontolog Oliver Rauhut usoudil, že zuby prostředního dinosauřího člena připisované L.? stechowi postrádají diagnostické znaky (unikátní odvozené znaky), a shodl se na tom, že tento druh je pochybné jméno. Rauhut poznamenal, že se stále dají odlišit od ostatních zubů teropoda ze souvrství Tendaguru, a to na základě jejich mírné rekurvace a bočního zploštění zubní koruny a širokých hřebenů na jazykovém boku (který směřoval dovnitř úst). L. sulcatus rozpoznal jako pochybné jméno, protože zub, který se na něj odkazuje, byl zobrazen pouze na jediném obrázku a nebyl řádně popsán v textu. Kromě toho původní pozůstatky Labrosaura neobsahovaly zuby a další druh, Labrosaurus ferox (nyní považovaný za synonymum k Allosaurus fragillis), byl založen na zubní kosti nesoucí zuby odlišné morfologie od zubů L. sulcatus. Rauhut tedy dospěl k závěru, že neexistuje žádný základ pro přiřazení zubů Tendaguru k Labrosaurovi. Předběžně je všechny kromě MB R 1084 odkázal na Ceratosaurus (pod názvem Ceratosaurus? stechowi), a to na základě anatomické podobnosti se zuby z tohoto rodu. Podle Rauhuta nepředstavují odlišné rysy mezi Janenschovými zuby typu b, c, e a d odlišné taxony, ale spíše variace podél zubní řady v čelistech zvířete. Rauhut také přiřadil ke stejnému taxonu další zub (MB R 1093), který popsal Janensch, ale o L.? stechowi se nemluví.
Rauhut také zjistil, že Janenschův typ a (MB R 1084) je tvarově odlišný od ostatních osmi zubů a možná představuje jiný taxon blízce příbuzný C.? stechowi. Uvedl některé rozdíly mezi ním a ostatními zuby původně označovanými L.? stechowi: MB R 1084 má více lingválních hřebenů (až jedenáct) a tři hřebeny a drážky na labiální straně, které směřovaly na vnější stranu tlamy. Navíc některé hřebeny MB R 1084 jsou omezeny na bázi koruny, spojeny delšími hřebeny táhnoucími se téměř po celé délce koruny, s 5 mm (0,20 in) vysokou oblastí na špičce zubu bez ozdob. Navíc hřebeny jsou přítomny téměř po celé přední tři pětiny koruny, zatímco zadní dvě pětiny jsou hladké. Směrem k přední části zubu je vroubkovaná část oddělena od cariny (řezné hrany) oblastí, která je mírně konkávní zepředu dozadu. Jediné podobnosti mezi zuby MB R 1084 a Middle Dinosaur Member spočívají v jejich celkovém tvaru a hustotě jejich zoubkování, protože všechny zuby mají 10 zubů na 5 milimetrů (0,20 palce) na zadní carině a 13 zubů na 5 milimetrů (0,20 palce) na přední carině.
V článku z roku 2012 Buffetaut použil MB R 1084 jako holotyp exempláře pro nový rod a druh Ostafrikasaurus crassiserratus a popsal jej jako raného teropoda spinosaurida. Jeho druhový název je odvozen z německého názvu kolonie, ve které byly fosilie nalezeny, Deutsch-Ostafrika, což znamená „Německá východní Afrika“, v kombinaci s řeckým σαῦρος (sauros), což znamená „ještěr“ nebo „plaz“. Konkrétní název pochází z latinského crassus, což znamená „tlustý“; a serratus, což znamená „zoubkovaný“, v odkazu na velké zoubky jeho zubů. Kvůli podobnosti s MB R 1084 přiřadil Buffetaut MB R 1091 od prostředního dinosauřího člena stejnému druhu. Oba zuby mají zakřivenou přední karínu, žádné boční zakřivení a srovnatelný tvar v průřezu. Mezi jejich hlavní rozdíly patří, že MB R 1091 má na jazykové straně pět podélných hřbetů ve srovnání s MB R 1084 s deseti, hřbety na prvním z nich jsou méně rozsáhlé. MB R 1091 měl také méně vrásčitou zubní sklovinu. Buffetaut poznamenává, že tyto rozdíly by mohly být vysvětleny individuálními odchylkami v rámci taxonu, ale protože oba zuby pocházely z různých členů formace Tendaguru, je odkaz pouze předběžný.
Buffetaut rozpracoval rozdíly mezi zuby Ostafrikasaurus crassiserratus a Janenschovy L.? stechowi morfootypy. Zuby Morphotype b (MB R 1083 a 1087) měly jak přední, tak i boční zakřivení a průřez ve tvaru písmene D. Morphotype c (MB R 1090) byl zakřivený ze strany na stranu, ale ne zepředu dozadu, nebyl zploštělý ze strany na stranu, měl zakulacenou přední část bez cariny a na jazykové straně nesl pět silných hřebenů, ale žádný na labiálním boku. Morphotype e (MB R 1092) připomínal typický zub teropoda. Je silně zploštělý ze strany na stranu, zakřivený zepředu dozadu, vykazuje 3 zubní protézy na milimetr (0,04 palce), jeho přední carina nesahá až k patě koruny a kromě slabé rýhy na koruně není žádná ozdoba a na jazykové straně jsou dva počínající hřebeny.
V roce 2020 studie zubů ze souvrství Tendaguru a z pozdní jury Jižní Ameriky opět naznačila identifikaci keratosauridu pro Ostafrikasaurus.
V roce 2016 španělští paleeontologové Molina-Pérez a Larramendi odhadovali Ostafrikasaurus na délku asi 8,4 metru (28 stop), výšku 2,1 m (6,9 stop) v kyčlích a hmotnost 1,15 tuny (1,27 krátkých tun; 1,13 dlouhých tun). Bez kompletnějšího materiálu, jako je lebka nebo tělesná fosilie, však nelze spolehlivě vypočítat velikost těla a hmotnost fragmentárních spinosauřích taxonů, zejména těch, které jsou známy pouze ze zubů. Odhady jsou tedy pouze orientační.
Holotyp zubu je tlustý, poněkud zploštělý do stran a od vrcholu ke dnu měří 46 milimetrů (1,8 palce). Jeho špička je zakulacená erozí a báze není zcela zachována. Koruna zubu má dobře definované cariny (řezné hrany), přední carina je zakřivená a zadní carina je téměř rovná. Je zde pouze mírné zakřivení ze strany na stranu. Obě cariny jsou zoubkované, se zaoblenými zubníky kolmými k okraji zubu. Vroubkované zuby nemají mezi sebou žádné inderdenticle sulci nebo drážky. Vytyčují přední carinu od báze ke špičce a pravděpodobně tak činily i na zadní carině, jejíž báze byla z velké části erodována. Směrem ke špičce zubu jsou tyto zoubky velmi opotřebované (zejména na přední carině). Na přední carině jsou dva zubníky na mm (0,04 palce) u špičky zubu a tři až čtyři na mm (0,04 palce), jak se zubníky smršťují k bázi koruny. Po celé zadní carině jsou dva zubníky na mm (0,04 palce). Zubky jsou výrazně větší než u všech ostatních známých spinosauridů.
Rauhut v roce 2011 o této interpretaci pochyboval a uvedl, že MB R 1084 má více podobností než rozdílů se zuby Ceratosaurus? stechowi, jako je zaoblený průřez, pouze okrajové zakřivení koruny, konvexnější jazykovou než labiální stranu a podobnou velikost a tvar zubů. Podle jeho analýzy tak zůstal jako jedinečný pro MB R 1084 pouze počet a rozložení hřebenů. Rauhut poznamenal, že ačkoli baryonychiny mají také hřebeny po obou stranách zubů, jsou obvykle nejvíce vyvinuté v zadní části zubu, zatímco MB R 1084 hřebeny na této straně postrádá. Tvrdí také, že vrásky, které Buffetaut pozoroval ve sklovině MB R 1084, jsou velmi slabé a do značné míry omezeny na jazykovou stranu, ve srovnání s nápadněji zrnitou texturou zubů Baryonyx. Podle Rauhuta, i když je MB R 1084 potenciálně spinosauridního původu, sdílí pouze obecnou podobnost s baryonychinovými zuby a místo toho pravděpodobně představuje blízkého příbuzného Ceratosaurus? stechowi. V Buffetautově pojmenování Ostafrikasaurus z roku 2012 ho umístil do Spinosauridae, místo toho tvrdil, že zub je velmi podobný zubům baryonychinů včetně Baryonyxe. Mezi jejich společné zubní rysy zahrnul lehké boční zploštění koruny, jemné smaltované vrásky a hřebeny na obou stranách, které nedosahují ke špičce zubu a jsou silnější a četnější na jazykové než labiální tváři. Pokud je tato identifikace správná, Ostafrikasaurus představuje jedny z nejstarších známých důkazů o spinosauridech.
Pojmenování a rozlišení nových dinosaurů pouze na základě zubů bylo paleontology často považováno za problematické, například u diskutované identity asijského rodu Siamosaurus. Buffetaut uvedl, že při důkladném porovnání a analýze morfologických znaků, jako je ozdoba, mohou být zuby teropoda dostatečně diagnostické, aby vyvolaly nové taxony. Mimoto zejména zuby spinosaurida mají jedinečnou morfologii velmi odlišnou od ostatních teropodů. Nicméně přesná identifikace Ostafrikasaura je stále nejasná a vědci poukázali na podobnosti v jeho ozdobné sklovině s Ceratosaurem, Paronychodonem, Zapsalisem, Acheroraptorem a Coelophysisem.
Fowler v roce 2007 předložil možnost, že se spinosauridi vyvinuli z předků keratosaurií, vzhledem k tomu, že baryonychinové zuby mají na svých korunách hřebeny připomínající ty, které jsou vidět na premaxilárních a zubních zubech Ceratosaurus. V roce 2008 Buffetaut tento návrh odmítl s poukazem na to, že D-tvarovaný průřez zmíněných zubů Ceratosaurus není přítomen v zubech baryonychinů.
Hlavní rozdíl mezi MB R 1084 a všemi ostatními známými spinosauridními zuby, jak poznamenal Buffetaut, byl ve velké velikosti zubů nesených carinae. To ho v roce 2008 přivedlo k hypotéze, že vývoj zubů spinosauridů je do značné míry charakterizován zmenšováním a případnou ztrátou zoubků. V roce 2012 Buffetaut předpokládal, že tento vzorec začne velkými zoubky u primitivních jurských taxonů jako Ostafrikasaurus (z tithónského věku), které se podobají typickým, podobně velkým teropodům. Ty se pak vyvinou do jemných, zmenšených a četnějších zoubků raně křídových baryonychinů, jako Baryonyx z barémie Evropy a Suchomimus z Aptianu do Albianu západní Afriky. Například Baryonyx měl sedm zubů na mm (0,04 palce) v porovnání s Ostafrikasaurusovými dvěma až čtyřmi. A konečně, zubní zuby by zcela zmizely u spinosaurů jako Spinosaurus z Albianu do Turonie severní Afriky. Buffetaut poukazuje na to, že silně zmenšené zoubkování u taxonů jako Siamosaurus, pocházející z Barremianu z Thajska, zřejmě představuje meziformu. Všiml si také podobnosti mezi chrupem Ostafrikasaurus a sadou zubů podobných Baryonyxu z předapského souvrství Cabao z Libye, s potenciálně důležitými biogeografickými důsledky. Tyto zuby jsou podobné svým celkovým tvarem, oválným průřezem a vrásčitým povrchem koruny, ale liší se tím, že mají menší zoubkování a flétny místo hřebenů.
Ve spojení s jejich mizejícími zoubky byly průřezy spinosauřích zubů zpočátku čepelovité a lentikulární v dřívějších taxonech jako Ostafrikasaurus a Baryonyx a v odvozených formách jako Spinosaurus se stávaly kruhovějšími. Ozdoba zubní skloviny spinosaura se však vyvíjela nepravidelněji než jejich zoubky a tvar průřezu. Většina neptačích teropodů měla zpravidla hladké zuby s nanejvýš minimálními vráskami. Ostafrikasaurovy zuby naproti tomu nesly silné podélné hřebeny, což je rys, který lze pozorovat i u Baryonyxe a jeho blízkých příbuzných, i když jejich význačnost se u jednotlivých taxonů liší. Spinosaurovy zuby, stejně jako u typických teropodů, byly obvykle hladké a asijské formy jako Siamosaurus vykazovaly zvýšený počet zubních hřebenů. Kromě toho byla zubní koruna vrásčitá u Ostafrikasaurus, Baryonyx a Suchomimus a asijských spinosauridů, ale hladká u Spinosaura, jen u některých exemplářů posledně jmenovaných byly patrné jemné vrásky.
V roce 2016 španělský paleontolog Aleandro Serrano-Martínez a jeho kolegové popsali možný zub spinosaurida, katalogizovaný jako MUPE HB-87, pocházející z nigerské Irhazerovy břidlice. Zub nalezený v souvislosti s kostrou sauropodního dinosaura Spinophorosaura pravděpodobně pochází z batonského stádia střední jury, 14 milionů let před Ostafrikasaurem. Pokud je tato identifikace správná, představuje MUPE HB-87 nejstarší známý důkaz spinosauridů ve fosilním záznamu. Na základě tohoto exempláře autoři navrhli nový evoluční model přechodu mezi „normálními“ zuby teropoda, k zubům spinosauridů. Zub je oválný v průřezu, je opakovaný a nese malé zoubky, stejně jako silné vroubkování, které nedosahuje ke špičce koruny.