The invention provides methods and compositions for rapid, sensitive, and highly specific nucleic acid-based detection of B. anthracis in a sample. In general, the methods involve detecting within the sspE gene of B. anthracis the presence of a fragment of six unique contiguous nucleotides that is not present in the sspE genes of other Bacillus bacteria or other non-Bacillus bacteria. In many embodiments, the methods involve amplifying a nucleic acid comprising at least a fragment of an sspE gene from a sample, and detecting the presence of the six unique contiguous nucleotide fragments in the nucleic acid. The invention also provides primers and kits for detection of B. anthracis in a sample. The subject invention finds use in a variety of different applications, including research, medical, diagnostic and military applications.