The Lazarus of the New Testament has two tombs because, by Eastern Orthodox tradition, he died twice. The first death is the famous one. Jesus arrives at Bethany after Lazarus has been buried for four days, asks where he has been laid, and calls him out of the tomb in front of his sisters Martha and Mary and a watching crowd. The first tomb still exists in Bethany, in the modern West Bank, attended now by a Christian shrine. After this resurrection, tradition says, Lazarus could not stay safely in Judea. Rumors of plots against his life forced him to flee, and he came to Cyprus. There, Paul the Apostle and Barnabas appointed him the first Bishop of Kition, the ancient city beneath modern Larnaca. He served thirty more years and was buried for the second and last time in his episcopal see. The Church of Agios Lazaros sits on top of that second tomb, the one with the inscription Leo VI's officials read in 890.

The 9th-century basilica is built of squared limestone blocks, each roughly a meter thick. The interior divides into three aisles, separated by bulky double pillars with arched openings cut through them. Originally three domes rose above the central aisle. Semi-cylindrical roofs covered the side aisles, intersected by cross-vaults. The sanctuary at the east end has a tripartite layout: three apses, semicircular inside but three-sided outside, with a five-sided central apse. An open porch leads down a few steps into the church. During the Frankish and Venetian centuries from the 13th through the 16th, the church became Roman Catholic, and a Gothic stone-covered portico, a stoa, was added on the south side. Walking around the building today, you can read three different architectural traditions in the masonry: the Byzantine basilica, the Gothic addition, and the later Latinate bell tower.

When the Ottomans took Cyprus from Venice in 1571, the three imposing domes of Saint Lazarus and the original bell tower were destroyed, almost certainly during the early years of Ottoman rule, and the church was converted into a mosque. The conversion did not last long. In 1589, the Ottomans sold the building back to the Orthodox Christians of Larnaca, probably because the Christian cemetery surrounding it made the site complicated for Islamic use. For the next two hundred years, the church functioned as something almost unique in the eastern Mediterranean: shared simultaneously by Orthodox and Catholic congregations. The porch still bears traces of inscriptions in Greek, Latin, and French left by visitors and parishioners of both rites. In 1857, after the Ottoman authorities again allowed Cypriot churches to have bell towers, the lost belfry was rebuilt in a Latinate style, a small architectural concession to the Catholic minority that had been worshipping there for two centuries.

The masterwork of the church is its iconostasis, the carved screen that separates the nave from the sanctuary. Between 1773 and 1782, the woodcarver Chatzisavvas Taliadorou produced one of the most ambitious Baroque iconostases in the Greek Orthodox world. From 1793 to 1797, the screen was gold-plated. The icons themselves were the work of several hands. Some were painted in the late 18th century by Michael Proskynetes, an icon painter from the village of Marathasa in the Troodos mountains. The painter Hatzimichael completed the program in 1797. Other furnishings, including a Rococo pulpit attached to one of the pillars (originally for Catholic use during the shared centuries), and various wall icons, date to the 17th century. A fire in 1970 damaged much of the interior, including substantial portions of the iconostasis and its corresponding icons. Restoration began immediately. The screen was partially rebuilt and re-plated with gold between 1972 and 1974, the work continuing right up to the year Cyprus was torn in half by war.

On 2 November 1972, during the post-fire renovations, workers lifted a section of flooring beneath the altar and discovered a marble sarcophagus containing human remains. The bones were identified as part of the relics of Saint Lazarus himself. Apparently, when Emperor Leo VI's officials had transferred Lazarus's body to Constantinople in 898, they had not taken everything. Some part of the saint stayed in Larnaca, beneath the floor of the church built over his second tomb. The relics that did go to Constantinople had a less peaceful future. They were looted by the Fourth Crusade in the early 13th century, brought to Marseille, and subsequently lost to history. The fragments left behind in 1972 are now back in their original setting, in the church that was built specifically for them. On Lazarus Saturday, eight days before Easter, the icon of Saint Lazarus is carried in procession through the streets of Larnaca, past the sea where ships from Constantinople once arrived, in front of the church that has held his tomb for over a thousand years.