Old English stridan (past tense strad, past participle striden), "to straddle, mount" (a horse), from Proto-Germanic *stridanan (source also of Middle Low German strede "stride, strive;" Old Saxon stridian, Danish stride, Swedish strida "to fight," Dutch strijden, Old High German stritan, German etreiten "to fight, contend, struggle," Old Norse striðr "strong, hard, stubborn, severe").
The sense connection in the various Germanic forms is perhaps "strive, make a strong effort;" the senses having to do with walking and standing are found only in English and Low German. 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.