Old English sang "art of singing, a metrical composition adapted for singing," from Proto-Germanic *sangwaz (cf. Old Norse söngr, Norwegian song, Swedish sång, Old Saxon, Danish, Old Frisian, Old High German, German sang, Middle Dutch sanc, Dutch zang, Gothic saggws), related to sing (q.v.).
Phrase for a song is from "All's Well" III.ii.9. With a song in (one's) heart "feeling of joy" is first attested 1930 in Lorenz Hart's lyric. Song and dance as a form of vaudeville act is attested from 1872; figurative sense of "rigmarole" is from 1895.