Old English stol "seat for one person," from Proto-Germanic *stōla- (source also of Old Frisian stol, Old Norse stoll, Old High German stuol, German Stuhl "seat," Gothic stols "high seat, throne"), from PIE *sta-lo-, locative of root *sta- "to stand, make or be firm."(source also of Lithuanian pa-stolas "stand," Old Church Slavonic stolu "stool").
Originally used of thrones (as in cynestol "royal seat, throne"); decline in sense began with adoption of chair (n.) from French, which relegated stool to small seats without arms or backs, then to "privy" (early 15c.) and thence to "bowel movement" (1530s).