1560s, "leisurely walk," from Middle French promenade (16c.), from se promener "go for a walk," from Late Latin prominare "to drive (animals) onward," from pro "forth" (see pro-) + minare "to drive (animals) with shouts," from minari "to threaten" (see menace (n.)).
Meaning "place for walking" is 1640s; specifically "walkway by the sea" late 18c.; British sense of "music hall favored by 'loose women and the simpletons who run after them'" is attested from 1863. Sense of "dance given by a school" is from 1887.