Botulinum neurotoxins (BoNTs), produced by spore-forming anaerobic Clostridium botulinum, are the most toxic substances known. They cause the life-threatening disease botulism, characterized by flaccid muscle paralysis. While the natural cases of botulism are rare, due to their extreme toxicity and easy production, BoNTs have become potential biowarfare agents, and create maximum fear among populations concerned with bioterror agents. The only available antidote against BoNTs is equine antitoxin. Equine antitoxin can only target the toxins at extracellular level, and can not reverse the paralysis caused by botulism. In addition, equine antibody can cause severe hypersensitivity reactions, and is limited to be used for prophylaxis treatment. BoNTs are large proteins with three distinct domains, the binding domain, the translocation domain, and the enzymatic domain with highly specific endopeptidase activity to cleave the proteins involved the neurotransmitter release. Targeting any of these domains can inhibit the functions of BoNT. Humanized monoclonal antibodies, small peptides and peptide mimetics, receptor mimics, and small molecules targeting the endopeptidase activity have emerged as potential new inhibitors against BoNTs. With the structure of BoNT resolved, molecular modeling and rational design of potent antidotes against botulism is on the horizon. An area that has not been explored for designing the antidotes against botulism is aptamers, which have been successfully developed as therapeutics in several areas. This review will focus on some of these new strategies to design effective antidotes against botulism. The strategies reviewed in this article can be easily applied to design inhibitors for other bacterial toxins.