The area of present-day Vanadzor has been settled since the Bronze Age, based on the tombs and other historic remains found on the nearby hills of Tagavoranist and Mashtots. During the ancient Armenian kingdoms, the area was considered as part of the Tashir canton of Gugark; the 13th province of the Kingdom of Armenia (Armenia Mayor), until the end of the Artaxiad Dynasty's rule over Armenia in the 1st century AD. Later, the region was ruled by the other Armenian dynasties of the Arsacids and the Bagratunis. By the end of the 10th century, the area became part of the Kingdom of Lori (Kingdom of Tashir-Dzoraget) until the beginning of the 12th century. With the invasion of the Seljuk Turks, the region came under the rule of the Great Seljuk Empire. The settlement was called Gharakilisa (meaning the black church in Turkic) by the Seljuks possibly as early as the 13th century, the name being taken from the black-stoned Armenian church of the Holy Mother of God on a nearby hill.
In 1801, the entire region of Lori became part of the Russian Empire along with the Georgian state. Lori was a strategically important territory for the Russian defensive forces on the border against Persia. In 1826, the settlement of Gharakilisa was entirely destroyed by Hasan Khan during the Russo-Persian war. In 1828, the Russians founded a new town as a major centre for the deployment of their troops during the Russo-Turkish War of 1828–29. According to Khachatur Abovian, the population of Gharakilisa was not more than 600 by the end of the 1820s, mainly consisting of migrants from Yerevan. In 1849, it became part of the Erivan Governorate within the Russian Empire. Under its new administrative status, Gharakilisa was flooded with many hundreds of migrating Armenian families from Kars, Ardahan and Western Armenian cities of Karin and Daroynk).
The town enjoyed a considerable uplift through the opening of the railroad towards Tbilisi in 1899. The vicinity of the town was the site of the Battle of Karakilisa in May 1918, when General Tovmas Nazarbekian's outnumbered troops, led by Garegin Nzhdeh successfully defended the region against the invading Turkish Army, pushing them back just few days after the crucial Armenian victory in the Battle of Sardarapat, thus allowing the Republic of Armenia to come into existence. On the North side of the Spitak-Vanadzor highway, about 2km West of the city, there is a little shrine in the ruins of a church, the site of a planned monument to that battle.
In 1920, after only 2 years of independence, Armenia fell under Soviet rule. The first city development plan for Gharakilisa, initiated by architects Karo Halabyan, Mikayel Mazmanyan and Gevork Kochar, was adopted in 1929–1930. Under the new plan, the town was enlarged towards the East and the West. In 1935, the Soviets renamed the city Kirovakan after the Bolshevik leader Sergey Kirov. In 1939, a new remodeling plan for the city, created by architects N. Zargaryan and A. Minasyan, was introduced to create an industrial district and a summer-resort area. The centre of the city was redeveloped during the 1950s. The central town square named after Sergey Kirov (now Hayk Square) was constructed along with the surrounding government and administrative buildings.
After the independence of Armenia, Kirovakan was renamed Vanadzor after the Vanadzor River that flows through the city.
Vanadzor, along with Gyumri and Spitak (25km west), suffered a considerable amount of damage from the 1988 earthquake when 564 residents died in the city. Unlike the two other cities, the majority of buildings in Vanadzor were unscathed from the earthquake.