late 14c., apparently just what it looks like: a fanciful name from Middle English tadde "toad" (see toad) + stole "stool" (see stool). Toads themselves were regarded as highly poisonous, and this word is "popularly restricted to poisonous or inedible fungi, as distinct from edible "mushrooms" [OED]. Compare toad-cheese, a poisonous fungi; toad's meat (1886), a "rustic" term for toadstool.