Paralytic shellfish toxins (PSTs) are non-protein neurotoxins produced by saltwater dinoflagellates and freshwater cyanobacteria. The ability of Lactobacillus rhamnosus strains GG and LC-705 (in viable and non-viable forms) to remove PSTs (saxitoxin (STX), neosaxitoxin (neoSTX), gonyautoxins 2 and 3 (GTX2/3), C-toxins 1 and 2 (C1/2)) from neutral and acidic solution (pH 7.3 and 2) was examined using HPLC. Binding decreased in the order of STX ~ neoSTX > C2 > GTX3 > GTX2 > C1. Removal of STX and neoSTX (77%–97.2%) was significantly greater than removal of GTX3 and C2 (33.3%–49.7%). There were no significant differences in toxin removal capacity between viable and non-viable forms of lactobacilli, which suggested that binding rather than metabolism is the mechanism of the removal of toxins. In general, binding was not affected by the presence of other organic molecules in solution. Importantly, this is the first study to demonstrate the ability of specific probiotic lactic bacteria to remove PSTs, particularly the most toxic PST-STX, from solution. Further, these results warrant thorough screening and assessment of safe and beneficial microbes for their usefulness in the seafood and water industries and their effectiveness in vivo.