Gavin Greig said it was made to fit Victorian times ('Greig-Duncan Folk Song Collection',I, #77), but noted there were earlier versions.
The earliest version is "The Recruiting Officer",(Over the hills and far away) which (with ABC of its tune), is in the Scarce Songs 2 file on my website (in Mudcat's Links). The latter first appeared in 'Pills to Purge Melancholy', 1706.