"walk in a vain, important manner, walk with affected dignity," 1590s, from Middle English strouten "display one's clothes proudly, vainly flaunt fine attire" (late 14c.), earlier "to stick out, protrude, bulge, swell," from Old English strutian "to stand out stiffly, swell or bulge out," from Proto-Germanic *strut- (source also of Danish strutte, German strotzen "to be puffed up, be swelled," German Strauß "fight"), from PIE root *ster- (1) "stiff."
Originally of the air or the attitude; modern sense, focused on the walk, first recorded 1510s. Related: Strutted; strutting. To strut (one's) stuff is first recorded 1926, from strut as the name of a dance popular from c. 1900. The noun meaning "a vain and affectedly dignified manner of walking" is from c. 1600.