El moment en què va sorgir la ciutat no ha pogut ser determinat, el document més antic que testimonia la seva existència és del 31 de març del 1243, es tracta d'un privilegi del rei Eric IV de Dinamarca atorgant a la ciutat els mateixos drets que tenia Viborg.[1] El 28 de febrer del 1459 el rei Cristià I de Dinamarca va prendre la ciutat sota la seva protecció. Els privilegis de la ciutat van ser confirmats el 19 d'abril del 1484, el 30 d'octubre del 1505 i el 23 de setembre del 1514.
L'església més antiga de la ciutat és la dedicada a Sant Olaf de Noruega (Sankt Olai), d'estil romànic del segle xii. L'església de Sant Joan (Sankt Hans) també seria del segle xii amb frescos datats el 1350,[2][3] mentre que la de Santa Caterina (Sankt Catharinæ) data de mitjans del segle xiii.
