O.E. steppan (Anglian), stęppan (W.Saxon) "take a step," from W.Gmc. *stap- "tread" (cf. O.Fris., M.Du., Du. stap, O.H.G. stapfo, Ger. stapfe "footstep"), from PIE base *stebh- "to tread, step" (cf. O.C.S. stopa "step, pace," stepeni "step, degree"). Originally strong (p.t. stop, pp. bestapen); weak forms emerged 13c., universal from 16c. Stepping stone first recorded early 14c.; in the figurative sense 1653. Step on it "hurry up" is 1923, from notion of gas pedal; step out (v.) is from 1907.
O.E. steppa (Mercian), stępe, stepe (W.Saxon) "stair, act of stepping," from the source of step (v.). Meaning "action which leads toward a result" is recorded from 1549. Stepladder (one with steps instead of rungs) is from 1751. Warning phrase watch your step is attested from 1934. Step-dancing first recorded 1886.