Much of our understanding of early eukaryote diversity and paleoecology comes from the record of organic-walled microfossils in shale, yet the conditions controlling their preservation are not well understood. It has been suggested that high concentrations of total organic carbon (TOC) inhibit the preservation of organic fossils in shale, and although this idea is supported anecdotally, it has never been tested. Here we compared the presence, preservational quality, and assemblage diversity of organic-walled microfossils to TOC concentrations of 346 shale samples that span the late Paleoproterozoic to middle Neoproterozoic in age. We found that fossil-bearing samples have significantly lower median TOC values (0.32 wt%, n = 189) than those containing no fossils (0.72 wt%, n = 157). Preservational quality, measured by the loss of surface pattern, density of pitting, and deterioration of wall margin, decreases as TOC increases. Species richness negatively correlates with TOC within the ca. 750 Ma Chuar Group (Arizona, USA), but no relationship is observed in other units. These results support the hypothesis that high TOC content either decreases the preservational quality or inhibits the preservation of organic-walled microfossils altogether. However, it is also possible that other causal factors, including sedimentation rate and microbial degradation, account for the correlation between fossil preservation and TOC. We expect that as TOC varies in space and time, so too does the probability of finding well-preserved fossils. A compilation of 13,940 TOC values spanning Earth history suggests significantly higher median TOC levels in Mesoproterozoic versus Neoproterozoic shale, potentially biasing the interpreted pattern of increased eukaryotic diversity in the Tonian.