To fully understand the evolution of today’s angiosperms, the fossil record of plant families and genera must be used to determine their time of origin and phytogeographic history. As within many angiosperm families, the interrelationships of extant Lythraceae are hard to resolve without sufficient data from the geological past. Here we establish the earliest fossil occurrences of Lythraceae and start resolving the interrelationships and evolution of two of its genera, Lythrum and Peplis. We studied several Cretaceous and Cenozoic palynofloras from the northern and southern hemispheres. Using the single-grain technique, we screened the treated samples for Lythrum- and Peplis-type pollen. The same individual pollen grains were observed under both the light- and scanning electron microscope, allowing a high taxonomic resolution to be achieved. Fossil Lythraceae pollen grains are rare in palynological samples. Nevertheless, we were able to identify Lythrum and Peplis pollen from Late Cretaceous sediments and thereby extend the fossil record of the two genera by ca 70 million years. The appearance of Lythrum and Peplis in North America and Peplis in Asia at approximately the same interval in the mid Late Cretaceous points to an already wide geographical distribution by then. These findings add vital information for the time of origin of the Lythraceae and suggest a higher diversity within the family. They also indicate that the distribution of particular genera during the Cretaceous was wider than previously thought.