According to the old Georgian annals, the church was built by the King Dachi of Iberia (circa 522-534) who had made Tbilisi his capital.

Originally dedicated to the Virgin Mary, it was renamed Anchiskhati (i.e., icon of Ancha) in 1675 when the treasured icon of the Savior created by the twelfth-century goldsmith Beka Opizari at the Ancha monastery in Klarjeti (in what is now part of northeast Turkey) was moved to Tbilisi to preserve it from an Ottoman invasion.

The icon was preserved at the Basilica of St Mary for centuries (it is now on display at the Art Museum of Georgia).

The basilica was damaged and rebuilt on several occasions from the 15th through 17th centuries due to wars between Georgia and the Persians and Turks.

During the Soviet period, all religious ceremonies at Anchiskhati Basilica were halted, and the building transformed into a museum for handicrafts.