The early folksong collectors (and the majority of today's revival performers) show a strong tendency to over-estimate the ages of songs and customs. That said, this custom does go back at the least to the 17th century.

Iona and Peter Opie (The Oxford Dictionary of Nursery Rhymes, 1951), give a composite set of 13 verses based on early printed sources, and comment:

"A folk-chant of considerable curiosity, which was embodied in nursery rhyme books at an early date.  It appears to be indigenous to all four kingdoms, and is likely to be exceptionally old.  In Ireland the characters have been recorded as "O, Andhra Roe, Brothers-in-Three, and the Kriggerawee"; in Wales, "Dibyn, Dobyn, Risiart, Robin, John, a y tri"; in Scotland, "Fozie Mozie, Johnie Rednosie, Foslin 'ene, and brither and kin".  A point common to all accounts of the hunt is the vast size of the quarry, doubts are expressed about the adequacy of the weapons, bows and arrows "will not do", it must be "great guns and cannon" (1927); there is a conference about how to bring the body home, and after a cart has been obtained, the lowland Scots ask, "What way will ye get her in?"  They needs must "drive down the door cheeks" (1776).  The dinner that the little bird's carcass will provide is such that the Manx would invite "King and Queen" and yet have enough over to give "eyes to the blind, legs to the lame, and pluck to the poor", while in some versions of the rhyme methods of disposing of the bones also engage discussion.  The hunting of the wren on Christmas morning (latterly on St. Stephen's Day) has been described by many folk-lore writers from the time of Aubrey (1696), who tells of "a whole Parish running like madmen from Hedg to Hedg a-Wren hunting", down to modern times (Sunday Express, 30 June 1946).  The rhyme was chanted in the ceremonial procession after the kill had been made.  Stories differ about why it should be the wren which is singled out for slaughter.  Those legends having purely local significance may be disregarded.  The wren has been looked upon as the king of birds in many countries, and the Druids are said to have represented it as such.  The story, quoted in Collecteana de rebus Hibernicis (1786), that the first Christian missionaries took offence at the respect shown to the wren, and commanded that it be hunted and killed on Christmas Day, has certainly a long tradition.  Sir James Frazer, however, suggests looking even deeper than this (Golden Bough, pt.V)."

They go on to cite a series of references, the earliest being Tom Thumb's Pretty Song Book, (M. Cooper), vol.ii, c.1744.  Mention is also made of an account by Sonnini, in his Travels, of wren-hunting near Marseilles in 1799.