Early attestations of the name during or following Slavic settlement include Cylia in 452, ecclesiae Celejanae in 579, Zellia in 824, in Cilia in 1310, Cilli in 1311, and Celee in 1575.

The proto-Slovene name *Ceľe or *Celьje, from which modern Slovene Celje developed, was borrowed from Vulgar Latin Celeae.

The settlement was known in the Celtic times and to Ancient Greek historians as Kelea;[5] findings suggest that Celts coined Noric money in the region.

It received municipal rights in AD 45 under the name municipium Claudia Celeia during the reign of the Roman Emperor Claudius (41–54).

Records suggest that the town was rich and densely populated, secured with the walls and towers, containing multi-storied marble palaces, wide squares, and streets.

The city was razed by Slavic tribes during the Migration period of the 5th and 6th centuries, but was rebuilt in the Early Middle Ages.

The first mention of Celje in the Middle Ages was under the name of Cylie in Wolfhold von Admont's Chronicle, which was written between 1122 and 1137.

It acquired market-town status in the first half of the 14th century and town privileges from Count Frederick II on 11 April 1451.

After the Counts of Celje died out in 1456, the region was inherited by the Habsburgs of Austria and administered by the Duchy of Styria.

The National Hall (Narodni dom), which hosts the Mayors Office and Town Council today, was built in 1896.

With the collapse of Austria-Hungary in 1918 as a result of World War I, Celje became part of the Kingdom of Serbs, Croats and Slovenes (later known as Yugoslavia).

The Gestapo arrived in Celje on 16 April 1941 and were followed three days later by SS leader Heinrich Himmler, who inspected Stari pisker prison.

During the war, the city suffered from allied bombing, aimed at important communication lines and military installations.

The coat-of-arms of Celje was selected for the national arms immediately after World War I in 1918, when Slovenia together with Croatia and Serbia formed the original Kingdom of Serbs, Croats and Slovenes (later Yugoslavia).

[citation needed] The current vice mayors of Celje are Saša Kundih, Samo Seničar and Uroš Lesjak.