The present Cathedral Church, as might be expected, has had many predecessors. The first was probably a megalithic temple built in Neolithic times. The Neolithic was ushered in Gozo 7,000 years ago, when humans first reached the island from Sicily. It is possible that Iċ-Ċittadella soon became a centre of activity: its position together with its covering of red top soil, considered sacred by the Neolithics, made it an ideal temple site, but successive civilizations wiped away the remains of previous settlements. The few trial excavations carried out so far have revealed a number of sherds from that period.
Iċ-Ċittadella became the focal point of Gozo around 1500 bc when it was fortified by the Bronze Age people (1500–700 bc) for the first time. This is amply proved by evidence from beneath the church and from the approach to Iċ-Ċittadella.
The Phoenicians, who colonized Malta and Gozo around 700 bc, raised a temple on the spot. During the Phoenician and, eventually, the Carthaginian domination, the Iċ-Ċittadella hill became the acropolis of the only town of gwl, the island of Gozo, and a temple was raised upon its highest point. A famous Punic inscription datable to the third century bc records a decree of the people of Gozo for the restoration of four temples. One of them was dedicated to Astarte, the principal Carthaginian goddess.
When the Romans took over in 218 bc, at the beginning of the second Punic War, they proceeded to worship in the same temple that was re-dedicated to Juno. This temple, entirely renovated during the early imperial period (27 bc–ad 14), dominated the acropolis and the town of gaulus that developed beneath.