The early history of Kars is little known, beyond that it had its own dynasty of Armenian rulers and was the capital of a region known as
Vanand. At some point in the 9th century (at least by 888) it became part of the territory of the Armenian Bagratids. For a short time (from 928 to 961) Kars became the capital of their kingdom. It was during this period that the Cathedral, later known as the Church of the Apostles, was built.