Fecal pellet-filled trace fossil Phymatoderma burkei from the Permian shallow-marine Teresina Formation (southern Brazil) was microscopically and geochemically investigated to reveal the significance of physicochemical processes in the preservation of invertebrate fecal pellets. Scanning electron microscope (SEM) analysis shows micron-sized spherules only in the pelletal infill of P. burkei, but not within the surrounding host sandstone. These spherules show highly uniform morphology and size (approximately 1 μm), and generally have hollow structures occasionally occurring as aggregates. Geochemically, such spherules are characterized by presence of Fe and Mn, occasionally with Ba. The evidence suggests that the spherules are mineral-replaced or mineral-encrusted microbial cells, which are most likely coccoid bacteria based on their morphological similarity. Within the fecal pellets excreted by the trace-maker of P. burkei, microbially mediated precipitation of Fe and Mn minerals probably occurred on or just near the outer surface of coccoid bacterial cells. Such microbial processes are important in the preservation of invertebrate fecal pellets excreted in shallow tiers, especially under wave- or current-influenced shallow-marine sedimentary conditions.