The area around Celje was inhabited as early as in the New Stone Age (Neolithic Era) and the Bronze Age. However, more complex settlement based on a more solid kinship and organization, with a stratified political and economic structure, could only be traced back to the Early Iron Age called the Hallstatt Era. The oldest remnants were found on Miklavški hrib which was also the location of a known Hallstatt hillfort.
It sat on the crest of the gill, not far from today's location of the St. Nicholas church. Although the natural soil erosion has taken its toll on the Hallstatt (Illyrian) hillfort, the archaeological excavations (remains of the former defence rampart with a ditch and small ceramic artefacts) undoubtedly point to the presence of Illyrians which have been found to have been present in this area from the early 1st century BCE to around 400 BCE when they were displaced by the stronger and more developed Celts. The hillfort was not large, but it is evidence of mass settlement of the area by the Illyrians. Thus, many other small objects for daily used were found along with foundations of residential buildings in the vicinity of Celje, for example on Rifnik (at Šentjur) and Brinjeva gora (at Zreče), while over sixty burial mounds with urns carrying the remains of cremated deceased.