Palms are a monophyletic group with a dominantly tropical distribution; however, their fossil record in low latitudes is strikingly scarce. In this paper, we describe fossil leaves, inflorescences, and fruits of palms from the middle to late Paleocene Cerrejón Formation, outcropping in the Ranchería River Valley, northern Colombia. The fossils demonstrate the presence of at least five palm morphospecies in the basin ca. 60 Ma. We compare the morphology of the fossils with extant palms and conclude that they belong to at least three palm lineages: the pantropical Cocoseae of the subfamily Arecoideae, the monotypic genus Nypa, and either Calamoideae or Coryphoideae. The fossil fruits and inflorescences are among the oldest megafossil records of these groups and demonstrate that the divergence of the Cocoseae was more than 60 Ma, earlier than has previously been thought. These fossils are useful in tracing the range expansion or contraction of historical or current neotropical elements and also have profound implications for the understanding of the evolution of neotropical rainforests.