Anthrax and botulism are dangerous infectious diseases that can be fatal unless detected and treated quickly. Fatalities from these diseases are primarily due to endopeptidase toxins secreted by the pathogens. Rapid and sensitive detection of the presence of active toxins is the key element for protection from natural outbreaks of anthrax and botulism, as well as from the threat of bioterrorism. We describe an ultrasensitive polymerase chain reaction (PCR)-based assay for detecting proteolytic activity of anthrax and botulinum toxins using composite probes consisting of covalent peptide–DNA conjugate for the detection of anthrax, and noncovalent protein-aptamer assembly to assay botulinum toxin activity. Probes immobilized on the solid-phase support are cleaved by toxins to release DNA, which is detected by real-time PCR. Both assays can detect subpicogram quantities of active toxins isolated from composite matrices. Special procedures were developed to isolate intact toxins from the matrices under mild conditions. The assay is rapid, uses proven technologies, and can be modified to detect other proteolytic and biopolymer-degrading enzymes.