A new crocodyliform, Sahitisuchus fluminensis gen. et sp. nov., is described based on a complete skull, lower jaw and anterior cervical vertebrae collected in the São José de Itaboraí Basin of Rio de Janeiro, Brazil. The specimen is one of the best preserved crocodyliforms from Paleocene deposits recovered so far and represents a sebecosuchian, one of the few clades that survived the Cretaceous-Paleogene biotic crisis. The new taxon is found in the same deposit as an alligatoroid, a group that experienced large diversification in the Paleogene. The sebecosuchian record suggests that after the Cretaceous-Paleogene biotic crisis, the less specialized members of this clade characterized by a higher number of teeth compared to the baurusuchid sebecosuchians survived, some having terrestrial habits while others developed a semi-aquatic life style (e.g., Lorosuchus). Starting in the Eocene, sebecid sebecosuchians became specialized with a more accentuated oreinirostry as observed in Sebecus and in Langstonia, but not showing the typical reduced dentition developed by the Cretaceous baurusuchid sebecosuchians. The basal position of Barinasuchus arveloi, a high-snouted Miocene sebecid, indicates the occurrence of an independent lineage sometime after the K-Pg biotic crisis that developed accentuated oreinirostry, suggesting a more complex history of the post-K-Pg crocodyliform radiation.