Possible early detection of people at increased risk for severe COVID-19 clinical course is extremely important so that appropriate therapy can be initiated promptly to prevent numerous deaths. Our study included 45 patients treated for COVID-19 at Dubrava University Hospital, with clinical course analysed from medical records and stool samples collected for determination of the gut microbiota diversity using 16S rRNA analysis. Sequencing was successful for 41 samples belonging to four clinical course groups (WHO guidelines): 12 samples—critical, 12—severe, 9—moderate and 8—mild group. Microbial composition was assessed between groups using two approaches—ANCOM (QIIME2) and Kruskal–Wallis (MicrobiomeAnalyst). On the genus level, two taxa were found to be differentially abundant: archaeal Halococcus and Coprococcus (for both W = 37)—the two were most abundant in the critical group (10% and 0.94% of entire abundance, respectively). Coprococcus catus was the only species identified by both methods to be differentially abundant between groups and was most abundant in the critical group. Alpha diversity indicated greater evenness of features in the critical group. Beta diversity showed clustering of samples from the critical group. A relationship between gut microbiota composition and the clinical course of COVID-19 disease was indicated, pointing towards specific distinct features of the critical group. In a broader sense, our findings might be useful in combating potential future similar pandemics and emerging virus outbreaks.