The first record of an insect (Coleoptera: Adephaga) from the base of Paleocene marine deposits in the Outer Flysch Carpathians of eastern Moravia (Czech Republic) is described. Its familial attribution to Gyrinidae or Haliplidae is critically discussed in comparison to fossil and recent representatives. The presence of a beetle elytron from hemipelagite in Early Paleocene deep-sea deposits is significant for taphonomy and suggests long wind transport from lagoonal to open marine environment and disarticulation by predators or scavengers in surface waters.