The aims of this study were firstly, to determine if the removal of heads and storage in a modified atmosphere (MA) extended the sensory shelf-life of chilled shell-on cooked Northern shrimp (Pandalus borealis). Secondly, the safe shelf-life of products was determined in regard to Listeria monocytogenes. Shrimp were kept whole or as tails (head region removed) at 5°C in laminar-film-bags with or without MA (40% CO2/60% N2) for 21 days. Analyses included changes in sensory properties (shelf-life), headspace CO2/O2, drip loss, pH, microbiota, total volatile nitrogen (TVN), trimethylamine-oxide (TMAO), and trimethylamine (TMA). Shrimp tails stored in MA reached the end-of-sensory-shelf-life after 21 days, followed by 18 days for whole shrimp in MA, and 14 and 11 days, respectively, for shrimp tails and whole shrimp without MA. For all four treatments, aerobic plate counts reached >8 log CFU/g at the time of sensory spoilage with Carnobacterium spp. and Pseudoalteromonas spp. dominating for shrimp with or without MA, respectively. Sensory spoilage coincided with TVN levels of 32–41 mg-N/100 g for shrimp in MA, while higher levels (66–143 mg-N/100 g) were observed for shrimp without MA. Pseudoalteromonas spp. had the strongest spoilage potential and likely contributed to the observed conversion of TMAO to TMA in shrimp stored without MA. Safe shelf-life was studied by testing the growth rate of L. monocytogenes, and the applicability of existing models to predict its growth. At 2°C–15°C, L. monocytogenes grew faster in whole shrimp than in shrimp meat. Moreover, the studied predictive model slightly underestimated growth of the pathogen. Taken together, our results show that to avoid unacceptable growth of L. monocytogenes, the safe shelf-life should be limited to less than 10 days at 5°C in MA for these ready-to-eat, cooked shell-on Northern shrimp products. Extension of product shelf-life would require research into stabilization of the products to inhibit the growth of L. monocytogenes.