Os bactérias não têm esqueletos ou carapaças duros. Se existissem fósseis de bactérias, como seriam formados? As bactérias são tão pequenas que, mesmo que fossem fossilizadas, como poderiam ser encontradas? Na verdade, as bactérias podem ser fossilizadas. Existe um grupo especial de organismos na natureza, chamados cianobactérias, que são um dos primeiros organismos da Terra. Os cientistas descobriram fósseis semelhantes a cianobactérias em estratos antigos de 3,5 bilhões de anos. As cianobactérias são maiores que a maioria das bactérias e podem secretar uma fina camada de parede celular. Mais importante ainda, as cianobactérias podem formar grandes estruturas em camadas, chamadas estromatólitos. Os estromatólitos são estruturas sedimentares biológicas formadas por microrganismos, principalmente cianobactérias, durante o crescimento e as atividades metabólicas, aderindo e precipitando sais inorgânicos ou capturando partículas minerais. Se estes estromatólitos forem moídos em finas lâminas, podem-se encontrar fósseis bem preservados de cianobactérias e algas. Na região de Zhangjiakou, de Xuanhua a Chicheng, na província de Hebei, na China, estratos do final do Eon Arqueano, há 1,8 bilhões de anos, contêm grandes quantidades de minério de ferro, que constituem o principal minério de ferro de Xuandong. Nos minérios de ferro de Xuandong e nos minérios de ferro associados de estromatólitos, foram descobertos fósseis de seis géneros de cianobactérias.
Além das cianobactérias, o número de bactérias fósseis não é muito grande. Sob condições químicas específicas, após as células bacterianas serem substituídas por sais inorgânicos, podem formar réplicas de células vivas ou pseudocristais. Algumas bactérias podem secretar uma camada externa de ferro e, por vezes, também se fossilizarem. Algumas bactérias podem penetrar nas conchas de animais ou em rochas, formando pequenos túneis dentro das conchas ou rochas, permitindo, assim, conhecer indiretamente os fósseis de conchas de animais de diferentes períodos. Além disso, o âmbar geralmente preserva um grande número de bactérias finas, algumas das quais podem sobreviver mesmo após centenas de milhões de anos. Também podem ser encontrados bactérias patogénicas em fósseis de ossos de animais, indicando que estes animais sofreram doenças causadas por bactérias durante a sua vida. As bactérias fósseis mais surpreendentes podem ser as magnetobactérias, que podem formar cristais de magnetita de tamanho nanométrico nas suas células. Os cristais de magnetita produzidos por estas bactérias podem ser distinguidos em rochas antigas de 2 mil milhões de anos e têm um tamanho de vários micrómetros, o que pode ser o fóssil mais pequeno de sempre.