Marked by his peers as an alchemist, astrologer, magician, and charlatan, Johann Georg Faust (circa 1480 or 1466 – circa 1541) is well known from writings from his contemporaries. Let us go trough some of the first mentionings of his.
1) Letter (August 20, 1507) from Benedictine Johann Tritheim (1462-1516) to the mathematician and astrologer Johann Windung: Tritheim, himself a magician, described Faust as a fool rather than a philosopher. In the letter we learn that Faust calls himself Magister Georgius Sabellicus Faustus Junior, but he is nothing more than a vain babbler, vagabond and mountebank who ought to be whipped. Tritheim writes that insane Faust boasted how Christ’s miracles were nothing to marvel at, since he could do the like whenever and as often as he pleased. He also could, apparently, restore all the works of Aristotle and Plato with great elegance from memory. From the letter we learn that Faust had to flee from the school of which he had been appointed master by the discovery of his unnatural crimes. By the words of Tritheim, he „fled from the city rather than confront him.“
2) Letter (October 3, 1513) from the jurist and canon Konrad Mudt to Heinrich Urbanus: second documented historical mention of Faust simply regards him as a charlatan, same as Tritheim did.
3) Fourth chapter of Index sanitatis**, Worms, 1539. by Philipp Begardi:** Faust is ranked among “wicked, cheating, useless and unlearned doctors.”
4) Sermones convivales**, Basel, 1543 by Johann Gast, Protestant pastor of Basel:** Now, this one is really interesting – for the first time we can observe shift in attitude towards Faust – Gast is first who credited him with genuine supernatural qualities. Gast claimed that he encountered Faust personally and that he believes how the necromancer is in league with the devil. He also claimed how horse and dog that accompanied Faust are evil spirits.
5) Locorum communium collectanea**, Basel, undated (mid 16th century) by Johann Mannel, councillor and historian to the emperor Maximilian II:** Mannel continued trend set by previous mentioning, remembering conversation he had with Philip Melanchthon (first systematic theologian of the Protestant Reformation, collaborator with Martin Luther) in which he described Faust as “a disgraceful beast and sewer of many devils,” accompanied by the devil himself in a form of a dog. In the end, Melanchthon claimed, Faust was killed by the devil, wringing his neck. Martin Luther himself proclaimed how by God’s help he had been able to ward off the evils which Faust with his sorceries had sought to put upon him.
6) De praestigiis daemonum**, Basel, 1563, by Johann Weiher, body physician to the duke of Cleves:** Weiher didn't believe in his superpowers, describing Faust as a drunken vagabond who had studied magic at Cracow, and before 1540 had practised “this beautiful art shamelessly up and down Germany, with unspeakable deceit, many lies and great effect.” Although he didn't believe in his superpowers, he did mention the tale of Faust being found dead with his neck wrung, after the whole house had been shaken by a terrific din.
This is an short overview how he appeared to his contemporaries. In the words of a historian W. A. Phillips, he was a: „a wandering charlatan who lived by his wits, cheiromantist, astrologer, diviner, spiritualist medium, alchemist, or, to the more credulous, a necromancer whose supernatural gifts were the outcome of a foul pact with the enemy of mankind. Whatever his character, his efforts to secure a widespread notoriety had, by the time of his death, certainly succeeded. By the latter part of the 16th century he had become the necromancer par excellence, and all that legend had to tell about the great wizards of the middle ages, Virgil, Pope Silvester, Roger Bacon, Michael Scot, or the mythic Klingsor, had become for ever associated with his name. When in 1587, the oldest Faust-book was published, the Faust legend was, in all essential particulars, already completed.“
To stress one issue further, first birth of his legend should be observed trough age which he lived in: the age of the Renaissance and the Reformation. Although age of intelectualism, it's important to note that it is also an age of superstition – alchemists searched for philosopher's stone while, for instance, da Vinci constructed his first machines. Further reading on social and political context of the age can be found in Sources mentioned at the end of the comment. As you mentioned Goethe, it is worth just to stress how during 18th century in Germany, during the literary revival, German authors searched for a national figure, myth, legend, something truly authentic for Germany, a well-worthy and interesting subject around they can form their national literature.
Sources:
Walter Alison Phillips, Faust, Encyclopædia Britannica, Volume 10, 1911
Frank Baron, Doctor Faustus: From history to legend, Humanistische Bibliothek, 1978
Leo Ruickbie, Faustus: The Life and Times of a Renaissance Magician, 2009.