It started (so far as we know) with Peter of Langtoft, an Augustinian canon and historian at Bridlington Priory who wrote a verse history called Langtoft's Chronicle, covering in Anglo-Norman 9000 verses the history of England from its founding by Brutus to the death of Edward I.
In it he tells the story of Guy, a page at the court of the Earl of Warwick, who falls in love with Felice, the earl's daughter. Well aware that she is far above his station, he sets out to prove his worth, ridding the countryside of dangers. These include dragons, giants, boars, and the Dun Cow. This is sufficient to win the hand of Felice.
Afterward, however, he is filled with remorse for his violent past. The solution is to go on pilgrimage to the Holy Land, but his time there motivates him to live a more humble life. He returns to England in secret and inhabits a cave overlooking the River Avon, living out his life as a hermit.
There's more, however, as the tendency of medieval writers to embellish meant there were many revisions and retellings. In one expanded version, he returns from the Holy Land after several years away in time to help King Æthelstan against invading northern kings. Winchester has traditions of this fighting. He then goes to Warwick in disguise where he takes the humble position of Felice's beadsman (a servant position whose duty is to pray for the souls of the deceased of the family). He eventually becomes a hermit and only reveals his true identity when he is about to die.
In the 14th century there were many new versions of the story in Middle English, mentioning his wars in Germany, Lombardy, and Constantinople. Because of the designation Guy of Warwick, a tower added to Warwick Castle in 1394 was named "Guy's Tower." There one can see Guy's sword and dining fork as well as his porridge pot. The 9th Earl of Warwick named his son Guy. The legend's popularity lasted a few centuries. Shakespeare mentions Guy (and the giant Colbrand that he defeats) in Henry VIII, and Colbrand again in King John. The numerous extant versions of the story have been gathered here.
We know what giants and dragons and boars are, but what was the deal with the "Dun Cow" that he defeated? Let's look into that tomorrow.