Old English steppan (Anglian), stæppan (West Saxon) "take a step," from West Germanic *stap- "tread" (source also of Old Frisian stapa, Middle Dutch, Dutch stappen, Old High German stapfon, German stapfen "step"), from PIE root *stebh- "post, stem; to support, place firmly on" (see staff (n.); source also of Old Church Slavonic stopa "step, pace," stepeni "step, degree"). The notion is perhaps "a treading firmly on; a foothold."
Transitive sense (as in step foot in) attested from 1530s. Related: Stepped; stepping. Originally strong (past tense stop, past participle bestapen); weak forms emerged 13c., universal from 16c. To step out "leave for a short time" is from 1530s; meaning "to go out in public in style" is from 1907. Step on it "hurry up" is 1923, from notion of gas pedal.
Old English steppa (Mercian), stæpe, stepe (West Saxon) "stair, act of stepping," from the source of step (v.). Compare Old Frisian, Middle Dutch, Dutch stap, Old High German stapfo, German Stapfe "footstep"). From late Old English as "degree on a scale." Figurative meaning "action which leads toward a result" is recorded from 1540s. In dancing, from 1670s. Meaning "type of military pace" is from 1798. Warning phrase watch your step is attested from 1911 (Wyclif (late 14c.) has keep thy foot in essentially the same sense). Step by step indicating steady progression is from 1580s. To follow in (someone's) steps is from mid-13c.