Nyborg was chosen because of where it is. Medieval Denmark was an archipelago of a kingdom, its power scattered across Jutland, Funen, Zealand and Scania, and the Danehof — the Danish medieval parliament, which mattered from roughly 1250 until 1413 — needed a site that no faction could claim as home ground. It had to gather somewhere central, and that was most often Nyborg Castle, sitting on Funen at the geographic heart of the Lands of Denmark. The palatium, the castle's residential range, was the assembly's principal venue until 1413. The 1282 charter set firmer rules around how the Danehof worked, turning what had been an occasional gathering of magnates into something closer to an institution — a place where the king had to appear, and answer.

The castle was established around 1170 by Knud Prislavsen, a nephew of Valdemar the Great, and was in royal hands by 1193. It is Denmark's oldest preserved royal residence. The original plan was severe and functional: a square, moated enclosure with corner towers linked by a curtain wall, the ring wall standing close to ten metres high, with projecting flanking towers and a heavy fortification tower. Comfort arrived later. A residential palatium was raised against the west wall in the mid-thirteenth century and a strong defensive tower went up on the east wall. Christian II was born here in 1481. Christian III, who stayed in the building often, added a new banqueting hall and a tower in the 1540s, and under Christian IV the Italian architect Domenicus Badiaz carried out further work in 1607, giving the main tower, Knudstårnet, a spire modelled on the Blåtårn in Copenhagen. Until 1560 Nyborg functioned as the nation's capital.

War ended it. The castle was badly damaged in the Dano-Swedish War of 1657–58, and afterwards most of the buildings were pulled down. From 1722 the stone was carted off to build Odense Palace — a medieval royal seat dismantled to furnish a baroque one. What survived spent roughly two and a half centuries in military hands, useful but unloved, and when the garrison finally left Nyborg in 1913 the remaining fabric was in a sorry state. Almost nowhere else in Denmark is the sequence so bare: the building where the crown's power was first written down became a building site, then a barracks, then a ruin.

Local interest saved it. Encouraged by the town, the National Museum of Denmark took on an extensive restoration under Mogens Clemmensen, working from careful archaeological investigation. The project ran about ten years before the money ran out in 1925, leaving much of the north wing and a good deal of interior detail unfinished. Clemmensen worked mainly from the castle's appearance under Christian III, but he also folded in details he found in other sources, and he did not always document which was which — so the Nyborg Slot a visitor walks through today is partly a building and partly an interpretation of one. Afterwards the rooms were furnished with pieces bought from historic manor houses. Three banqueting halls each stand for a different Danish century: the Danehofsalen, where the parliamentary meetings were held; Margrethe's Hall, where court representatives of the Kalmar Union met; and Christian III's Hall, which carries a display on the period when Nyborg was the capital.

Nyborg Slot is run as part of Østfyns Museer, formed in 2009 by the merger of Kerteminde Museum and Nyborg Museum, an organisation whose reach traces the eastern half of Funen: the castle itself along with Borgmestergården in Mads Lerches Gård, the Johannes Larsen Museum at Kerteminde, and the Viking Museum at Ladby, where Denmark's only Viking Age ship burial lies in the ground. The most recent chapter has been harder than the medieval one. A major restoration began in the autumn of 2017, aiming to complete the surviving royal wing and add some two thousand square metres of new exhibition space by 2023. On 17 December 2020 the Environmental and Food Appeals Board ruled against the scheme, finding that the planned construction could not go ahead as designed, and on 8 February 2022 the A.P. Møller Foundation withdrew its funding, citing the project's postponed timetable. Eight centuries after Erik Klipping was made to sign, the castle is still arguing with the authorities.