Teleosts form the largest clade among the extant actinopterygians, some extinct forms of which are still poorly positioned in the phylogeny. The Tselfatiiformes and Araripichthyidae are such examples. A newly discovered genus and species from the Cenomanian of Haqel, Lebanon, is described, and its systematic affinities are discussed. It shares several characteristics (deep and compressed body with elongated and high dorsal and anal fins, edentulous maxilla, and sinusoidal vertebral column) with both the Tselfatiiformes and Araripichthys, making it difficult to place within the teleosts. It shares with Abisaadichthys, among the tselfatiiforms’ family Protobramidae, an autogenous retroarticular, and with Araripichthys premaxillae with a long ascending process, well-developed maxillary articular condyle and two supramaxillae. Moreover, it shows some unique characteristics (a thin maxilla with two large supramaxillae, fused articular and angular bones, mandibular sensory canal opening on the external side of the anguloarticular, first dorsal pterygiophore having the same enlarged semi-circular plate as the first anal pterygiophore) justifying its generic status. Comments on some of the protobramids are presented, and the necessity for phylogenetic analysis to place the Tselfatiiformes, Araripichthys and Ypsiloichthys within the teleosts is outlined.