The first documentary mention of Coburg occurs in 1056, in a gift by Richeza of Lotharingia to the Archbishop of Cologne, to allow the creation of Saalfeld Abbey. In 1075, a chapel dedicated to Saint Peter and Saint Paul is mentioned at the Coburg fortress. This document also refers to a Vogt named Gerhart, implying that the local possessions of the Saalfeld Benedictines were administered from the hill.
In the 13th century, the hill overlooked the important trade route from Nuremberg via Erfurt to Leipzig. At the time, the town was controlled by the Dukes of Merania (or Meran). They were followed in 1248 by the Counts of Henneberg who ruled Coburg until 1353, save for a period from 1292-1312, when the House of Ascania (Askanien) was in charge.
In 1353, Coburg fell to Friedrich, Markgraf von Meißen of the House of Wettin. His successor, Friedrich der Streitbare was awarded the status of Elector of Saxony in 1423. Coburg was now referred to as “Saxony”. The fortifications of the Veste were expanded in 1430 as a result of the Hussite Wars.
In 1485, in the Partition of Leipzig, Veste Coburg fell to the Ernestine branch of the family. A year later, Elector Friedrich der Weise took over the rule of Coburg.
Johann der Beständige used the Veste as a residence from 1499. From April to October 1530, during the Diet of Augsburg, Martin Luther sought protection at the Veste, as he was under an Imperial ban at the time. Whilst he stayed at the fortress, Luther continued with his work translating the Bible into German.