The history of Nové Zámky is often associated with the medieval period, when four medieval villages — Nyárhíd, Gúg, Györök and Lék — were located in the area of present-day Nové Zámky. The actual founding of Nové Zámky is, in the specialist literature, considered to have been the construction of the first Nové Zámky fortress on the left bank of the river Nitra in 1545. The first Nové Zámky fortress was built by the Archbishop of Esztergom, Pál Várday, to protect the territories belonging to the Esztergom Archbishopric after Esztergom was occupied by the Ottomans.
The second, modern Renaissance fortress was built in swampy terrain on the right bank of the river Nitra between 1573 and 1580. The new fortress was built according to plans by the Italian architect Ottavio Baldigara and had the shape of a hexagonal star.