This study investigated the physico-chemical and microbiological changes occurring during the processing of fresh king fish (Scomberomorus tritor) into Lanhouin, a traditional fish-based condiment obtained by natural fermentation in West-Africa. A total of 121 isolates of coagulase-negative Staphylococcus (CNS) have been collected during two variants of fermentation trials and identified by PCR multiplex and Staph Array methods. The physico-chemical results showed that moisture content and water activity decreased while total volatile nitrogen increased during the processing. In contrast, there was no linear relationship between biogenic amines content and fermentation time whatever the variant of technology used since the biogenic amine values did not increase continuously as fermentation progressed. Pathogenic bacteria increased during the ripening and decreased as the fermentation progressed whereas CNS were enumerated along with the two variants of fermentation and reached approximately 4 Log CFU/g from the 3rd day to the end of fermentation. CNS species belonging to S. nepalensis, S. sciuri, S. cohnii subsp. cohnii, S. saprophyticus, and S. epidermidis were identified during the two fermentations processes. S. nepalensis and S. cohnii were isolated along with the two fermentations, attesting that they were well adapted to these processes.