Останки Эокархарии были найдены в 2000 году экспедицией Чикагского университета во главе с Полом Серено. Типовой вид Eocarcharia dinops был описан им совместно со Стивеном Брусатти в 2007 году, а научное описание вышло в журнале Acta Palaeontologica Polonica в 2008 году. Родовое название буквально означает «ранняя акула», по словам исследователей, ссылаясь на базальное положение вида в пределах семейства Кархарадонтозаврид, где эпоним Carcharodontosaurus — «акулозубый ящер». Видовое название означает «ужасная морда» либо «свирепые глаза», ссылаясь на большой костный хребет над глазницей.
Голотип MNN GAD2 состоит из лобной и посторбитальной частей черепа. Многие другие фрагменты черепа вероятно принадлежат другим особям данного вида. Находка была сделана в формации Elrhaz (апт — альб) недалеко от деревни Gadoufaoua в районе Тенере, где также были найдены и другие виды динозавров: Suchomimus и Kryptops.
Точный размер Эокархии является неопределённым в связи с отсутствием достаточного количества ископаемого материала, кроме черепа, но Серено оценивает размер динозавра — до 8—12 метров в длину. Так же он помещает род Eocarcharia на филогенетическом древе в базальную позицию семейства Кархарадонтозавров, указывая на тесное сходство с акрокантозавром.