From what I can find, they existed in written form from quite early in the 13th century, and it wasn't until the 19th century that the veracity of the event was challenged.
From the wiki on Sangerkreig:
The oldest poetic accounts, dating from the 13th century, describe specific episodes of the contest such as the Fürstenlob and the Rätselspiel.
The Fürstenlob ("princely praise") was a contest among six minstrels: Heinrich von Ofterdingen, Walther von der Vogelweide, Biterolf, Reinmar von Zweter, Wolfram von Eschenbach and Heinrich Schreiber. The six singers were placed before the Count and Countess of Thuringia, in order to determine which best understood how to sing praises of a prince. Heinrich von Ofterdingen was the most eloquent, but earned the envy of the other minstrels, who tricked him into earning a death sentence. Heinrich gained the protection of Countess Sophia and a one-year reprieve, during which he went to Hungary and sought the assistance of the sorcerer Klingsor. Heinrich and Klingsor returned to Thuringia to resume the contest.
The Rätselspiel ("mystery game") was the subsequent poetic duel between Wolfram von Eschenbach and the Hungarian sorcerer Klingsor. Wolfram proved himself capable and eloquent, and when Klingsor grew weary he summoned a demon to continue the duel. When Wolfram began to sing of the Christian mysteries, the demon was unable to respond.
The book Kierkegaard Journals also references it as a 1260 work of anonymous poems (Much snipped) and also mentions the Furstenlob and the Ratelspiel:
...the anonymous cycle of poems "Sangerkrieg auf der Wartburg" [Poetic Contest at the Wartburg Castle] from ca. 1260 ...
The Brothers Grimm also describe it in their German Legends from 1816 (emphasis mine):
The original poetry, which is at least partially in almost all medieval song manuscripts, must have been written down in the 50s of the 13th century, the dating of the singer war by the Brothers Grimm is - but if you look at those involved - but sure chosen wisely
So it looks like the legend arises from works in the 1250's, and only relatively recently was the veracity of the events challenged.