The aim of this study was to investigate the microbial quality of whole Norway lobster (Nephrops norvegicus) and Norway lobster tails to optimize handling conditions. This was done by assessing the total viable count (TVC) and characterizing the dominant microbiota. The cultivable microorganisms were quantified via classical microbiological plating methods. To characterize as many bacterial species present as possible, we performed advanced molecular identification techniques (PCR-DGGE). The initial TVC of fresh Norway lobster meat was high (3.0 log cfu/g) as compared to fish. No significant difference between whole Norway lobster and Norway lobster tails could be found during the storage period. From day 6 of storage, a significant difference between Plate Count Agar (PCA) and Marine Agar (MA) was observed. The microbiota of Norway lobster was dominated by members of the Gram-negative genera such as Psychrobacter spp., Pseudoalteromonas spp., Pseudomonas spp., Luteimonas spp., and Aliivibrio spp. From these bacteria, mainly Psychrobacter spp. and Pseudomonas spp. remained present until the end of the storage period. These are known spoilage organisms in fishery products. Other known spoilage organisms of crustaceans such as Photobacterium spp. could not be identified.