According to Emmanouela Grypeou and Helen Spurling (The Book of Genesis in Late Antiquity, Brill 2013, p71ff), the earliest Christian reference to this idea is Origen (c. 184-253), who traces it to Jewish tradition:
Concerning the place of the skull, it came to me that Hebrews hand down [the tradition that] the body of Adam has been buried there; in order that 'as in Adam all die' both Adam would be raised and 'in Christ all will be made alive'. (Commentary on Matthew, 27.32, original in Greek; later Latin translation here does not mention any Jewish tradition)
Essentially the same story is recounted by:
- A text of c.325-350 attributed, probably falsely, to Athanasius of Alexandria (c.297-373)
- John Chrysostom (c.347-407) in a homily on John's gospel, 19:16, says "Some say that Adam died there, and there lies; and that Jesus in this place where death had reigned, there also set up the trophy."
- A fifth or sixth century commentary on Isaiah, attributed, again probably falsely, to Basil the Great (329-379)
- Epiphanius of Salamis (c.310-403) in his Panarion 46.5, against the Tatianists, says Adam "was buried there, on the site of Golgotha. This is probably the way the place, which means 'Place of a Skull', got its name, since the contour of the site bears no resemblance to a skull."
- Basil of Seleucia (d. 458) in his Sermon 38 (Patrologia Graeca 85.409)
- Jerome (347-420) in his commentaries on Matthew 27:33 and Ephesians 5:14, both written in 398; though he finds the story doubtful.
Even at this stage of Christian history, there was some doubt about the archaeological truth of the story, despite its tempting doctrinal resonance (Christ as the second Adam). The location of the crucifixion was not known with any certainty; still less, the burial place of Adam, which Jerome instead located in Hebron. If Adam's skull is buried under Golgotha, and if the Holy Sepulchre is indeed built on top of Golgotha, then the skull is somewhere under the church.
Regardless, it is still a very old story, as the examples above show.