The Cathedral has no building inscriptions - very unusual for such an important structure built during the Bagratid period. Inscriptions probably did exist, but were removed by the later Muslim occupants of the building. All medieval authors refer to it simply as "the Cathedral". The name "Holy Apostles" is first recorded in the 19th century, and refers to the 12 figures carved on the drum of the dome.

According to the tenth century Armenian historian Stephanos Asoghik, the Bagratid king Abas (who ruled from 929 to 953) "...built the holy Cathedral of the city of Kars ... with stone blocks polished with steel ... surmounted by a circular dome whose ornamentation resembled the vault of heaven". Stephanos continues, saying that this happened "...at that time Lord Anania was on the patriarchal throne". Anania was patriarch between the years 943 and 967. Construction of the Cathedral probably started shortly after Abas's coronation and was completed by the mid 940s.

The common assertion that after the Seljuk Turks captured Kars in 1064, the Cathedral was abandoned for several hundred years is not credible given the prominence of the structure. There are also traces (staining on the stone walls) of what is probably a zhamatun built against the western facade - this is unlikely to date from before 1064 and is probably from the early 13th century.

In 1579 the Ottoman Turks converted the church into a mosque. After the Russians captured Kars in 1877 the building was converted into a Russian Orthodox church. It was used mainly by the Russian military and was known as the "fortress cathedral". Small porticoes were added in front of the north, south and west entrances, and a sacristy constructed against the east wall. Inside the church an ornate stone iconostasis was built across the apse, and the walls were painted and given decoration and Cyrillic inscriptions in gold paint. A little later (the mid 1890s?) an elaborate belltower was constructed just to the north of the Cathedral. Strangely - considering it was built to serve what was now a Russian Orthodox church - it was a copy of the 13th century belltower at the Armenian monastery of Haghbat.

After the fall of the Kars to the Turks in 1918, the Cathedral was turned back into a mosque. In 1919, following the retreat of the Turks, it returned briefly to its original function as an Armenian church, only to be turned into a mosque again in 1920 when the Turks recaptured Kars. Like most Armenian property in Kars, the church was confiscated and became the property of the Turkish state. They sold it to the Kars municipality, who had planned to demolish it and build a school on the site. This plan was fortunately never carried out, although the Russian belltower was destroyed. In the 1950s it was used as a depot for petroleum. During the 1960s and 1970s it housed a small museum. After this museum was transferred to a purpose built building, the church lay abandoned and increasingly derelict. In 1999 work began to convert it into a mosque.

The figure above the western entrance is probably the most important - it is emphasised by birds carved on the capitals of the columns below it (all the other capitals are plain). This figure (number one in the above drawing) has a serpent at each side of his head, and probably represents Saint Gregory the Illuminator - the snakes referring to his years of confinement in a snake filled dungeon. The other figures may represent the Twelve Apostles (minus Judas, presumably). Most are depicted with their arms stretched upward (in a praying position?) or placed across their chests. One figure (number two) stands beside a tree, another (number five) appears to carry a hammer-like tool.

The conical roof of the cupola rests on a cornice carved with an interlaced band of four strands. The cornice below the lower roofs has a band of intersecting lozenges linked like a chain. The windows of the drum are plain, but the lower windows have hooded mouldings.