The timing of origin of eukaryotes and the sequence of eukaryogenesis are poorly constrained because their fossil record is difficult to interpret. Claims of fossilized organelles have been discounted on the unsubstantiated perception that they decay too quickly for fossilization. We experimentally characterized the pattern and time scale of decay of nuclei, chloroplasts, and pyrenoids in red and green algae, demonstrating that they persist for many weeks postmortem as physical substrates available for preservation, a time scale consistent with known mechanisms of fossilization. Chloroplasts exhibit greater decay resistance than nuclei; pyrenoids are unlikely to be preserved, but their presence could be inferred from spaces within fossil chloroplasts. Our results are compatible with differential organelle preservation in seed plants. Claims of fossilized organelles in Proterozoic fossils can no longer be dismissed on grounds of plausibility, prompting reinterpretation of the early eukaryotic fossil record and the prospect of a fossil record of eukaryogenesis.