The present study aimed to evaluate the dynamic changes of the microbial diversity, physicochemical and sensory qualities of sodium alginate-coated catfish (Clarias gariepinus) flesh during cold storage at 4 ℃ and to examine the correlation between them. High-throughput sequencing technology was used to analyze the structure of microbial community. The physicochemical parameters investigated included water-holding capacity (WHC), pH, total volatile base nitrogen (TVB-N) content, thiobarbituric acid reactive substances (TBARs) value, and biogenic amine contents. The results showed that the microbial diversity diminished with storage time. At the initial stage of storage, the dominant bacteria were Psychobacterium, Acinetobacter, and Streptococcus. The dominant bacteria in the late storage period were Lactococcus, Orthomonas, Morganella, and Shewanella. The pH and sensory quality gradually decreased during cold storage. The contents of TVB-N, TBARs, cadaverine, putrescine, and tyramine gradually increased with storage time, and TVB-N content was (30.69 ± 1.92) mg/100 g on the 10th day, exceeding the safe upper limit. Correlation analysis showed that the count of Lactococcus was positively correlated with the levels of spoilage indicators such as TVB-N content, TBARs value, histamine and tyramine contents.