Large numbers of well-characterized clinical samples are fundamental to establish relevant associations between the microbiota and disease. Formalin-fixed and paraffin-embedded (FFPE) tissues are routinely used and are widely available clinical materials. Since current approaches to study the microbiota are based on next-generation sequencing (NGS) targeting the bacterial 16S rRNA gene, our aim was to evaluate the feasibility of FFPE gastric tissues for NGS-based microbiota characterization. Analysis of sequencing data revealed the presence of bacteria in the paraffin control. After the subtraction of the operational taxonomic units (OTUs) present in the paraffin control to the FFPE tissue sample dataset, we evaluated the microbiota profiles between paired FFPE and frozen gastric tissues, and between different times of archiving. Compared with frozen gastric tissues, we detected a lower number of OTUs in the microbiota of paired FFPE tissues, regardless of the time of archiving. No major differences in microbial diversity were identified, but taxonomic variation in the relative abundance of phyla and orders was observed between the two preservation methods. This variation was also evident in each case and throughout the times of FFPE archiving. The use of FFPE tissues for NGS-based microbiota characterization should be considered carefully, as biases can be introduced by the embedding process and the time of tissue archiving.