early 13c., "to stumble over a tree-stump or other obstacle" (obsolete), from the source of stump (n.). From 1590s as "reduce to a stump." Sense of "walk stiffly and clumsily" is first recorded c. 1600. Sense of "baffle, bring to a halt by obstacles or impediments" is first recorded 1807, American English, perhaps in reference to plowing newly cleared land, but compare earlier sense "to challenge, dare" (1766).
Meaning "go on a speaking tour during a political campaign" is from 1838, American English, from phrase stump speech (1820), large tree stumps being a natural perch for rural orators (this custom is attested from 1775), especially in new settlements. Related: Stumped; stumping.