The initial building was founded by Constantine I of the Roman Empire in 335, after he had removed a Roman temple on the site that was possibly the Temple of Aphrodite built by Hadrian. Constantine had sent his mother Helena to find the site; during excavations she is said to have discovered the True Cross. The church was built around the excavated hill of the Crucifixion, and was actually three connected churches built over the three different holy sites.
This building was damaged by fire in 614 when the Persians invaded Jerusalem. Under the Muslims it remained a Christian church, but the original building was completely destroyed on October 18, 1009, by the "mad" Fatimid caliph al-Hakim.
However, the foundation was retained, and the church was rebuilt by Constantine IX Monomachos in 1048. The rebuilt church was taken by the knights of the First Crusade on July 15, 1099. Crusader chief Godfrey of Bouillon, who became the first king of Jerusalem, decided not to use the title "king" during his lifetime, and declared himself Advocatus Sancti Sepulchri, "Protector (or Defender) of the Holy Sepulchre." The Crusaders began to renovate the church in a Romanesque style and added a bell tower. These renovations were completed during the reign of Queen Melisende 50 years later in 1149.
The church was an inspiration for churches in Europe like Santa Gerusalemme in Bologna.
The Franciscan monks renovated it further in 1555, as it had been neglected despite increased numbers of pilgrims. A fire severely damaged the structure again in 1808, causing the dome to collapse. The current dome dates from 1870. Extensive modern renovations began in 1959, including a redecoration of the dome from 1994-1997.
Several sects cooperate, sometimes acrimoniously, in the administration and maintenance of the church and its grounds. The three appointed when Crusaders held Jerusalem are the Greek Orthodox, the Armenian Apostolic and Roman Catholic churches. These remain the primary custodians of the church. In the 19th century, the Coptic Orthodox, the Ethiopian Orthodox and the Syrian Orthodox acquired lesser responsibilities, which include shrines and other structures within and around the building. An agreement regulates times and places of worship for each Church. A neutral neighbour Muslim family has for centuries been the custodian of the keys.
Many secular modern scholars believe that Calvary, also known as Golgotha, probably lies outside of Old Jerusalem. "Calvary" and "Golgotha" derive from the Latin and Aramaic words for skull. At a site outside of the Old City walls there is a rock formation that indeed resembles a skull.