Wadi El-Hitan, the UNESCO World Heritage Site, of the Fayum Depression in the northeast part of the Western Desert of Egypt, has produced a remarkable collection of Eocene vertebrates, in particular the fossil whales from which it derives its name. Here we describe a new genus and species of marine catfishes (Siluriformes; Ariidae), Qarmoutus hitanensis, from the base of the upper Eocene Birket Qarun Formation, based on a partial neurocranium including the complete left side, partial right dentary, left suspensorium, two opercles, left pectoral girdle and spine, nuchal plates, first and second dorsal spines, Weberian apparatus and a disassociated series of abdominal vertebrae. All of the elements belong to the same individual and some of them were found articulated. Qarmoutus gen. nov. is the oldest and the most complete of the Paleogene marine catfishes unearthed from the Birket Qarun Formation. The new genus exhibits distinctive features not seen in other African Paleogene taxa, such as different sculpturing on the opercle and pectoral girdle with respect to that on the neurocranium and nuchal plates, denticulate ornamentation on the skull bones arranged in longitudinal rows and forming a radiating pattern on the sphenotic, pterotic, extrascapular and the parieto-supraoccipital, indentations or pitted ornamentation on the nuchal plates as well as the parieto-supraoccipital process, strut-like radiating pattern of ornamentation on the opercle from the proximal articulation to margins, longitudinal, curved, reticulate ridges and tubercular ornamentations on the cleithrum, sinuous articulation between the parieto-supraoccipital process and the anterior nuchal plate, long, narrow, and arrowhead shaped nuchal shield, very small otic capsules restricted to the prootic. Multiple parsimony and Bayesian morphological phylogenetic analyses of Ariidae, run with and without "molecular scaffolds", yield contradictory results for the placement of Qarmoutus; the genus is either a phylogenetically basal ariid, or it is deeply nested within the ariid clade containing New World species of Sciades.