Recent studies on the ant phylogeny are mainly based on the molecular analyses of extant subfamilies and do not include the extinct, only Cretaceous subfamily Sphecomyrminae. However, the latter is of major importance for ant relationships, as it is considered the most basal subfamily. Therefore, each new discovery of a Mesozoic ant is of high interest for improving our understanding of their early history and basal relationships. In this paper, a new sphecomyrmine ant, allied to the Burmese amber genus Haidomyrmex, is described from mid-Cretaceous amber of France as Haidomyrmodes mammuthus gen. and sp. n. The diagnosis of the tribe Haidomyrmecini is emended based on the new type material, which includes a gyne (alate female) and two incomplete workers. The genus Sphecomyrmodes, hitherto known by a single species from Burmese amber, is also reported and a new species described as S. occidentalis sp. n. after two workers remarkably preserved in a single piece of Early Cenomanian French amber. The new fossils provide additional information on early ant diversity and relationships and demonstrate that the monophyly of the Sphecomyrminae, as currently defined, is still weakly supported.