Starch is a major component in the human diet, and the acquisition of starch-rich food sources is considered a pivotal step in the biological and cultural evolution of humankind. However, the potential role of starch as an energy vector in paleo-ecosystems has never been addressed, obviously due to the lack of tangible records of preQuaternary starch grains. Here we describe similar to 280-m. y.-old lycopsid megaspores from Permian forest-swamp deposits in north China that bear caps of granular material. Size, shape, and surface structures as well as chemical and optical properties of these grains show that these caps are masses of compound storage starch. This is by far the oldest unequivocal record of fossil starch known to date. Deposition outside the actual megaspore container makes it unlikely that these starches were used for embryo nutrition; moreover, ultrathin sections of the megaspores indicate that they may have been produced after the megaspores were fertilized. By analogy to the elaiosomes on seeds of zoochorous plants today, we suggest that these starch caps were used to attract and reward animals, possibly land arthropods or snails, for megaspore dispersal. This study offers a rare glimpse into early stages of plant-animal co-evolution in Permian swamp-forest ecosystems.