In 1905, British archaeologists Archibald H. Sayce and Somers Clarke reported on the find of a granite block bearing the name of king Khasekhemwy at the Upper Egyptian site of Elkab. The block was brought to the Egyptian Museum in Cairo, but although currently lost, it constitutes decisive evidence of the existence of an Early Dynastic temple at the site of Elkab. Although the approximate location where the block was discovered is known, the area has never been subjected to a thorough archaeological investigation. In this paper we present the results of archaeological investigations carried out in that area, with the objective to verify the presence of such an Early Dynastic building and to investigate its role in the local and regional cultic landscape. The results, although not meeting the original objective, allow to understand the area’s stratigraphy and add two new structures to the archaeological map of Elkab. These consist of a mud brick enclosure, probably of fairly recent date, and the subterranean part of a stone building that, based on the ceramic evidence, is to be dated in the Roman period, possible the 2nd century AD.