Effective cooling of newly caught fish is of great importance to inhibit bacterial growth and therefore increase quality, safety and shelf life of the product. In this study, two commercial cooling media (liquid ice A and B) were tested and their performance was compared to conventional plate ice during chilled 8-day storage of whole, gutted haddock. Temperature was monitored, and deteriorative changes were followed by conventional microbiological counts [(total viable psychrotrophic; specific spoilage organisms and physicochemical methods (pH, TVB-N, TMA, salt content)]. A cultivation-independent method (16S rRNA clone analysis) was used to study the effect of cooling treatments on the bacterial community of haddock initially and at the end of storage. The results show that the bacterial growth behavior observed for differently cooled fish was not supported by their temperature profiles. Growth of the SSOs, Photobacterium phosphoreum and H2S-producing bacteria was delayed at early storage, independently of the cooling methods. With further storage, little or no count differences were seen among traditionally iced fish and those cooled in liquid ice with a top ice layer. At the end of storage, significant (p < 0.05) increase in P. phosphoreum and H2S-producing bacteria counts of skin and flesh sampled from liquid ice with no top ice layer was observed along with higher salt, TVB-N and TMA flesh content. Cultivation-independent analysis confirmed the dominance of P. phosphoreum in fish stored in liquid ice B with no top layer (up to 76% dominance) and liquid ice A with top layer (44% dominance). Psychrobacter and Flavobacterium dominated the microbiota of fish stored in conventional plate ice and liquid ice B with ice top layer. The study shows that the use of liquid ice prepared from brine provides faster initial cooling of whole fish but may create unfavorable conditions under extended storage where the active spoiler P. phosphoreum becomes dominant. Plate ice may therefore be an optimal medium for extended fish storage.