Церква Святого Миколая вперше письмово згадується в 1279 році. За традицією вважається, що вона була побудована Біргер Ярлом, засновником самого міста Стокгольм.

Майже чотириста років церква була єдиною прихідською церквою в місті, адже інші церкви схожого віку спочатку слугували духовним потребам релігійних громад (напр., Церква Риддаргольм).

Церква стала належати до лютеранського протестантизму в 1527 році. З Середньовіччя будучи прихідською церквою для Миколаївського приходу, який покривав весь острів, на якому розташоване Старе місто, вона також є Стокгольмським собором з часу створення Стокгольмської діоцезії в 1942 році.

Через свій зручний розмір та розташування поруч зі старим королівським замком та сучасним королівським палацом, церква часто була місцем основним подій у шведській історії — коронацій, королівських весіль та похорон. Останнім шведським королем, який був коронований у цій церкві, був Оскар II в 1873. Кронпринцесса Вікторія, найстарша дочка короля Карла XVI Густафа та королеви Сільвії) вийшла заміж за Даніеля Вестлінга в церкві Святого Миколая 19 червня 2010 року, в той самий день, коли і її батьки побралися в цій церкві в 1976 році.