The construction of the building began in 1225. the church achieved parish church status in 1255 and was completed by 1273-75. It was originally built as a Romanesquebasilica with two choirs. During the 14th century several important changes to the construction were made: first the side aisles were widened and the steeples made higher (1309–1345), then the late gothic hall chancel was built (1358–1379). The two towers were added in the 15th century. In the middle 17th century galleries were added and the interior was remodelled in the Baroque fashion. The church suffered serious damage during World War II and was subsequently restored. Some of the old interior undamaged includes the Shrine of St. Sebaldus, works by Veit Stoss and the stained glass windows.
The church had an organ by the 14th century, and another by the 15th. The main organ had been built in 1440–41 by Heinrich Traxdorf, who also built two small organs for Nuremberg's Frauenkirche. Until its destruction in the 20th century it was one of the oldest playable organs in the world, and all the more notable because Traxdorf was one of the first organ builders to depart from the gothic Blockwerk organ by dividing the windchests and separating the front stops into Flute (Principal) and Octave (see pipe organ). The Traxdorf organ was rebuilt in 1691. The modified case was destroyed by the Allied forces during a bombing raid on 2 January 1945.
The new 4 manual, 122 rank, 84 stop organ by Peter of Köln was installed in 1975.
The position of organist of St. Sebaldus was the most important one of this kind in Nuremberg, and several important composers occupied this post. Organists who worked at St. Sebaldus include the following (almost all held the post until their death, except where stated otherwise):