This icon dates back to the late 16th–early 17th century and depicts the two leading Apostles of church, Saint Peter and Saint Paul, founders of Christian faith in the West and East respectively. It is the work of a very remarkable Cretan painter, Emmanuil Lombardos or Lambardos, and it symbolizes the indivisible unity of the Church. This image, as well as several of the relics found in the church, traveled from afar to arrive in Lindos, as a result of the intense maritime activity of its inhabitants.

An interesting story reports that this icon remained buried for many years in the Harbor of Agioi Apostoloi (Holy Apostles). It was discovered there along with the ruins of an ancient church dedicated to Saint Paul during the course of an excavation. It is reported that Saint Paul had disembarked at that very spot in 57 A.D., in order to preach the word of God. In accordance with a number of sources, this spot was revealed by Saint Paul himself to the officer Karydis' daughter in a dream. She then traveled to Lindos and indicated to the local villagers the spot where the old church of the Apostle was buried. The church seen there today was built over the ruins of the older one in 1951.