Marine toxins appear to be increasing in many areas of the world. An emerging problem in the Mediterranean Sea is represented by palytoxin (PlTX), one of the most potent marine toxins, frequently detected in seafood. Due to the high potential for human toxicity of PlTX, there is a strong and urgent need for sensitive methods toward its detection and quantification. We have developed an ultrasensitive electrochemiluminescence-based sensor for the detection of PlTX, taking advantage of the specificity provided by anti-PlTX antibodies, the good conductive properties of carbon nanotubes, and the excellent sensitivity achieved by a luminescence-based transducer. The sensor was able to produce a concentration-dependent light signal, allowing PlTX quantification in mussels, with a limit of quantification (LOQ = 2.2 μg/kg of mussel meat) more than 2 orders of magnitude more sensitive than that of the commonly used detection techniques, such as LC-MS/MS.