We report a new proviverrine hyaenodontid creodont mammal, Boualitomus marocanensis, n.g., n.sp., from the earliest Eocene of Morocco, and provide new comments on Tinerhodon from the late Paleocene of Morocco. Aside from the autapomorphic loss of P/1, Boualitomus is characterized by a primitive morphology (e.g. M/3 subequal to M/2, short molar trigonid, narrow talonid, metaconid comparable to paraconid) which resembles most closely the proviverrine Prototomus. Boualitomus is more primitive than Prototomus, especially in its small size and the talonid of P/4 not being fully simplified, bearing at least two accessory cusps including a bulbous protostylid. These primitive features are remarkably reminiscent of Tinerhodon. The morphological relationship of Boualitomus and Tinerhodon supports the proviverrine affinity of the latter. Significant basal hyaenodontid synapomorphies of Boualitomus and Tinerhodon are the paraconid and paracristid development in M/1–3, anterior premolar morphology and occurrence of diastemata. Boualitomus and Tinerhodon throw new light upon the question of the origin of the Creodonta. Tinerhodon further fills the structural gap between Hyaenodontidae and primitive insectivore-like eutherians, and it provides additional data for the hypothesis of a didelphodontan origin for the Creodonta. The presence of cimolestids (as the stem-group of hyaenodontids) in the late Paleocene of Morocco, and the identification of Boualitomus and Tinerhodon as the most primitive and earliest known Hyaenodontidae, support an African origin of the family and its order.