Nyborg Municipality as an administrative region has existed since the rule of Valdemar II of Denmark, who granted Nyborg the rights of a market town (Danish: Købstad).

A royal charter from 1193 indicates that the city has been granted the status of a market town even earlier.

Among those privileges were the fact that the merchants of Vindinge Hundred had to go to Nyborg to sell their wares.

The privileges were expanded in 1446, where the merchants of Gudme Hundred also had to go to Nyborg with their wares.

Harbours between Kerteminde, Svendborg and Slipshavn were also outlawed, and Nyborg was given permission to arrange a large yearly market.

Fiefs (Danish: Len) were dissolved and the country split into several amts.

It also included ten birks: Hindsholm, Holckenhavn, Ravnholt, Glorup, Hesselager, Brahetrolleborg, Holstenshuus, Vantinge, Avernakø and Strynø.

The reason was that the new Kerteminde Municipality would have too small of a population to function properly.

In the end, Nyborg and Kerteminde weren't merged and became two separate municipalities.

Smaller villages in the municipality included Frydenlund, Bovense, Nordenhuse, Skaboeshuse, Regstrup, Skalkendrup, Korkendrup, Sulkendrup and Kogsbølle.