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.
c. 1300, dance, daunce, "succession of steps and movements, commonly guided by musical accompaniment," also "a dancing party," from dance (v.). From late 14c. as "a tune to be danced to."
With many figurative senses: in Middle English the olde daunce was "the whole business," and the daunce is don was exactly equivalent to modern slang phrase the jig is up. To lead (someone) a dance "lead in a wearying, perplexing, or disappointing course" is from 1520s. Dance-band is from 1908; dance-floor from 1863; dance-hall from 1823.