Merriam-Webster dates the phrase to 1818. Most websites that tell this story trace the practice to Norsemen (Vikings). Seems like a rather large gap in time.