New coleoid cephalopods, assignable to the order Sepiida, are recorded from the Selandian/Thanetian boundary interval (Middle to Upper Paleocene transition, c. 59.2 Ma) along the southeastern margin (Toshka Lakes) of the Western Desert in Egypt. The two genera recognised, Aegyptosaepia n. gen. and ?Anomalosaepia Weaver and Ciampaglio, are placed in the families Belosaepiidae and ?Anomalosaepiidae, respectively. They constitute the oldest record to date of sepiids with a ‘rostrum-like’ prong. In addition, a third, generically and specifically indeterminate coleoid is represented by a single rostrum-like find. The taxonomic assignment of the material is based on apical parts (as preserved), i.e., guard, apical prong (or ‘rostrum-like’ structure), phragmocone and (remains of) protoconch, plus shell mineralogy. We here confirm the shell of early sepiids to have been bimineralic, i.e., composed of both calcite and aragonite. Aegyptosaepia lugeri n. gen., n. sp. reveals some similarities to later species of Belosaepia, in particular the possession of a distinct prong. General features of the phragmocone and protoconch of the new form are similar to both Belocurta (Middle Danian [Lower Paleocene]) and Belosaepia (Eocene). However, breviconic coiling and the presence of a longer ventral conotheca indicate closer ties with late Maastrichtian–Middle Danian Ceratisepia. In this respect, Aegyptosaepia n. gen. constitutes a link between Ceratisepia and the Eocene Belosaepia. The occurrence of the new genus near the Selandian/Thanetian boundary suggests an earlier origin of belosaepiids, during the early to Middle Paleocene. These earliest known belosaepiids may have originated in the Tethyan Realm. From northeast Africa, they subsequently spread to western India, the Arabian Plate and, probably via the Mediterranean region, to Europe and North America.