Once the body dies, the indigenous microbes of the host begin to break down the body from the inside and play a key role thereafter. This study aimed to investigate the probable shift in the composition of the rectal microbiota at different time intervals up to 15 days after death and to explore bacterial taxa important for estimating the time since death. At the phylum level, Proteobacteria and Firmicutes showed major shifts when checked at 11 different intervals and emerged at most of the postmortem intervals. At the species level, Enterococcus faecalis and Proteus mirabilis showed a downward and upward trend, respectively, after day 5 postmortem. The phylum-, family-, genus-, and species-taxon richness decreased initially and then increased considerably. The turning point occurred on day 9, when the genus, rather than the phylum, family, or species, provided the most information for estimating the time since death. We constructed a prediction model using genus-level data from high-throughput sequencing, and seven bacterial taxa, namely, Enterococcus, Proteus, Lactobacillus, unidentified Clostridiales, Vagococcus, unidentified Corynebacteriaceae, and unidentified Enterobacteriaceae, were included in this model. The abovementioned bacteria showed potential for estimating the shortest time since death.