In the second half of the 12th century, Count Hermann von Wolweswac founded the town of Neustadt with the building of a castle. Governance of the city was left to the Counts of Andechs, the later Dukes of Meranien. Neustadt is first mentioned in a document from the 16th of June, 1248, describing the "market forum" ("Marktflecken") of Neustadt. In 1316, Neustadt was designated a City, and in 1353, Neustadt came under the care of Coburg, making it a possession of the House of Wettin, which is remained until the First World War. Under Wettin rule, the city acquired the two-tailed, red and black lions which grace its coat of arms.
Neustadt lay on a major trade route between Nürnberg and Leipzig, and in the 14th century, the city received a parish church. By the end of the Middle Ages, the city had a population of roughly 570.
By the time the Thirty Years' War began, Neustadt's population had grown to roughly 1000. When the war began, the leaders of Coburg declared their neutrality. However, because the trade route on which Neustadt lay came to be used as a route of transportation by the various combatants, the city suffered greatly. Still greater damage came in 1636, when a large fire, unrelated to the war, which burnt down over half of the city.
In 1839, a second, larger fire destroyed 179 of the city's 226 houses, as well as the city hall and archives, and heavily damaged the church.
End of World War I, decision to join Bavaria
When the First World War ended in 1918 and the Weimar Republic was founded, the Duchy of Saxe-Coburg-Gotha ceased to be a duchy. At first, it formed the Free State of Coburg. This state proved so small as an administrative unit that the decision was made to have the Free State become a part of either Thuringia or Bavaria. A referendum, held in 1919, saw Neustadt (and the rest of the Free State of Coburg) decide, by overwhelming majority, against Thuringia and thus for Bavaria. Neustadt politician and industrialist Max Oscar Arnold had actively campaigned for union with Bavaria.