The coralline genus Phymatolithon Foslie 1898 (Corallinaceae, Rhodophyta) is a well-known present-day genus. Owing to the traditional taxonomic characters applied to fossil coralline algae it has, however, not been possible to identify this genus in fossil material until recently. This paper presents the first documentation of a fossil Phymatolithon by applying generic features used in present-day coralline algal taxonomy and discusses its separation from other genera in fossil material. These features are (1) arrangement of basal filaments, (2) occurrence of cell fusions, (3) relative length of subepithallial initials, (4) conceptacle perforation. The stratigraphic distribution of Phymatolithon could be extended from Lower Eocene to Recent. As it is a typical non-tropical genus in present-day environments, designation of Phymatolithon can give valuable indications for palecological reconstructions. The studied material comes from Late Eocene red algal limestones of the Austrian Molasse Zone.