Signs of human activity dating back to about 4000 BCE have been found, but there are no signs of permanent settlements from that time.
Archaeological excavations indicate that the first town dates back to the 11th century and consisted of two settlements, one in the western part of the medieval city encircled by what are now the streets of Mikkel Bryggersgade, Vestergade, Gammeltorv/Nytorv and Lĝngangsstrĉde, roughly corresponding to the coastline of the time, and another smaller settlement at what is now Kongens Nytorv. The surrounding area consisted of moist beach meadows and signs of cattle grazing have been found. The city probably had a harbour located at present day Hĝjbro Plads. Details of the existence of a small town as early as the 11th century have recently been published by Videnskab.dk with a series of articles documenting new archeological finds. These provide evidence of a large estate at today's Kongens Nytorv, a church close to the later St Clemens, a market, at least two wells and many smaller habitations spread over a fairly wide area.