According to Frank Shay, American Sea Songs and Chanteys from the Days of Iron Men and Wooden Ships, this simple shanty may date as early as the reign of Henry VIII (early 16th century).
The song was used to unify a single pull during the first word of the chorus: Haul. It was therefore useful when adjusting the mightiest of sails, such as getting the foresheet hauled aft. Frank T. Bullen describes a New Zealand cruise in which their crew over-zealously hauled so hard the large rope snapped and the crew fell prostrate "as if sticken down by lightning" ("Songs of the Fo'cas'le", Evening Star, Issue 111554, Feb. 13 1900 pg. 6).
Several writers go out of their way to mention that by the time of recording (1800s and 1900s), the bowline referred to a weak rope used to extend and keep from shaking the weather leech (edge) of foresail or mainsail. It did not require collective force or shanty to haul. Nevertheless, the song saw great popularity for its use in the fore and main sheet.
The James Madison Carpenter entry for this song recalls an incident of tug-of-war between sailors and soldiers in Aberdeen in the mid-1800s. The sailors put this song to use and won.