“尼堡”这个名字出现的最早记录可以追溯到1193年,一篇文献中提到了尼堡城堡——这座中世纪城堡至今仍然耸立在城市之中。而城镇本身的名字至到1202年才被提及。在17世纪,尼堡与腓特烈西亚(Fredericia)及哥本哈根(Copenhagen)并列丹麦的三座重镇之一。每一个都毗邻一处重要的水源——对尼堡来说就是大贝尔特海峡(Storebælt)。

1659年,城市被瑞典占领,后又被丹麦盟友荷兰派出的远征军解放。

1867年,城堡被废弃,而城镇也向堡垒以外不断扩张。在此期间城市南部的堡垒遭到了破坏并被改造成居民区。西部和北部的大部分堡垒则保留了下来,并且构成了被称为“Nyborg Voldspil”的年度戏剧表演的舞台,这是丹麦最古老的户外剧场。

从1183年至1413年,尼堡成为丹麦国家立法与司法大会“Danehoffet”的集结之地。在此期间尼堡也被看作是丹麦的首都。丹麦与挪威国王克里斯蒂安二世(1481-1559)就出生于尼堡城堡。

2005年,扩建尼堡港的规划正式启动,这个在1996年之前将菲英岛与西兰岛相连接的旧轮渡码头已经被数个大型奢华公寓楼所代替。