Tropical shrimp is of considerable economic importance in the word but is highly perishable due to microbial and chemical degradation. Biopreservation is a food preservation technology based on the addition of “positive” bacteria able to kill or prevent the growth of undesirable microorganisms. Two strains of lactic acid bacteria (LAB) have previously been selected for a biopreservation strategy: Lactococcus piscium CNCM I-4031, for its ability to prevent the sensory deterioration of seafood and Carnobacterium divergens V41, which inhibits growth of Listeria monocytogenes. The objective was to test the association of the two strains to improve both the quality and safety of shrimp. In a first trial, the two LAB were inoculated alone or in a cocktail in cooked and peeled shrimp (CPS) Penaeus vannamei at 5 × 105 CFU/g. Chemical, sensory and microbiological analyses by culture-dependent and -independent methods were performed during storage under modified atmosphere packaging (MAP) at 8 °C. The results were compared to a non-inoculated batch. In a second trial, the same experiments were repeated in the presence of 102 CFU/g of L. monocytogenes RF191. The microbiota of CPS was composed of LAB, Shewanella spp. and Enterobacteriaceae. Brochothrix thermosphacta was not detected. L. piscium and C. divergens reached 108 and 109 CFU/g, respectively, in 7 days and did not inhibit each other when co-inoculated. L. piscium reduced L. monocytogenes by 1 Log (CFU/g) for 28 days. C. divergens had an immediate listericidal effect lasting 7 days. A regrowth of L. monocytogenes was then observed but the count was always 2 to 5 Log (CFU/g) lower than in the control. No additional or synergic effect between protective strains was observed and the cocktail had the same inhibitory effect as C. divergens alone. C. divergens was very effective at preventing the sensory deterioration of CPS. This may be related to the inhibition of Shewanella and Enterobacteriaceae. However, the panelists could detect the presence of C.divergens during the first 10 days of storage, with slight unpleasant odors and flavors. L. piscium improved the sensory quality of CPS for 14 days only. In co-culture, L. piscium eliminated the off-odors and flavors released by C. divergens in the early stage of storage and the co-culture allowed maintaining a good quality of CPS throughout the storage. Therefore, the use of a cocktail of L. piscium CNCM I-4031 and C. divergens V41 is recommended in a strategy of biopreservation of shrimp.