The fossil record of Eusuchia extends back to the Early Cretaceous (Barremian), with the English species Hylaeochampsa vectiana being the oldest known representative of the clade so far. However, the eusuchian record from the Barremian to the Santonian is scarce and fragmentary worldwide. Here we described a new eusuchian crocodylomorph based on a partial skull and lower jaw from the Early Upper Cenomanian of the Tentugal Formation, in the Baixo Mondego region, west-central Portugal. The specimen exhibits a series of characters not seen in other taxa, allowing its assignment to a new genus and species named Portugalosuchus azenhae gen. et sp. nov. The results of a cladistic analysis place this specimen within Crocodylia, as the sister taxon to all other non-gavialoid crocodylians. Therefore, this Portuguese specimen represents the only well-documented and valid eusuchian species in the Cenomanian in Europe, and may be the oldest representative of Crocodylia known so far, helping to fill a gap in the fossil record of Eusuchia from the Barremian to the Campanian. In addition, the discovery of this new taxon sheds light on the radiation of Eusuchia and the origin of Crocodylia, which probably took place in Europe.