The tune first appears in the William Ballet Lute Book (1595), and was printed in "much altered" form in Playford's Dancing Master of 1650-51. There is a town of Staines on the Thames River, but no one seems to know if it has anything to do with the title. The tune was used for a morris dance of the same name in the Cotswold village of Longborough, Gloucestershire. It was printed in Chappell Popular Music of the Olden Time, vol. 1 (1859), Sharp's Country Dance Tunes, (1909/1994) Hesperus on Early American Roots (1997) and Williamson's English, Welsh, Scottish and Irish Fiddle Tunes (1976). This tune is also used for "Blessed Be That Maid Mary" which is in the Christmas section.