Well-preserved fossil eggs and eggshell fragments from the Pliocene Apolakkia Formation of Rhodes (Greece) are described. The eggs were found in-situ in a clutch. They are sub-spherical with lengths of 53-60 mm and widths of about 40 mm. All eggs are diagenetically compressed and their original diameters are estimated at 45-50 mm. The eggshells are 0.3-0.5 mm thick, partly recrystallized, but widely still aragonitic. They consist of needle-like crystals that form individual shell units. A few pores are preserved between these shell units. This shell-structure allows assignment to chelonian eggs in the oofamily Testudoolithidae and the oogenus Testudolithus. The external morphology, microstructure and mineralogical composition of the eggshells show close resemblance to eggs of the extant tortoise Geochelone elephantopus. Together with a small association of turtle carapace fragments from the same formation, the clutch represents the first discovery of turtle and reptilian remains from the Pliocene of the island of Rhodes.