Old English stridan "to straddle," from Proto-Germanic *stridanan (cf. Middle Low German strede "stride," Dutch strijd, Old High German strit, German Streit "fight, contention, combat," Old Norse striðr "strong, hard, stubborn, severe"), from root *strid- "to strive, make a strong effort." Meaning "to walk with long or extended steps" is from c.1200. Cognate words in most Germanic languages mean "to fight, struggle;" the notion behind the English usage might be the effort involved in making long strides, striving forward.
"a step in walking," Old English stride, from the root of stride (v.). Figurative meaning in make strides "make progress" is from c.1600. To take (something) in stride (1832), i.e. "without change of gait," originally is of horses leaping hedges in the hunting-field; figurative sense attested from 1902. Jazz music stride tempo is attested from 1938.