According to an ancient inscription, it was founded by the exarch Isaac of Ravenna in 639.
The original church is believed to have had a nave with one aisle on each side and a single apse on the eastern wall of the cathedral. It is difficult to tell what the original church was like because very little of it survived the subsequent renovations. Much of the plan of the original church survives as its present form is very similar to the original but the only physical parts that survive are the central apse wall and part of the baptistery that survives as part of the façade of the current church.
The first of two major renovations occurred in 864 under the direction of Bishop Adeodatus II. In this renovation, the two aisle apses that appear today were built. Also, the synthronon that fills the central apse was created and the crypt was placed under it. After this renovation, the cathedral would have resembled the current cathedral more than the original church would have but it is not until after the second and final major renovation that the cathedral appears very similar to its current design.
The final renovation was consecrated under Bishop Orso Orseolo, whose father Pietro Orseolo II was the Doge of Venice at the time, in 1008. With this renovation, Orseolo raised the nave, added windows to the western wall, and created the arcade that runs along the nave on both sides separating it from the aisles and helping to support the clerestory.